配点 : 800800

問題文

NN 個の正整数列からなる数列 A=(A0,A1,,AN1)A=(A_0,A_1, \dots , A_{N-1}) が与えられます。
数列 AA に対して以下の [操作] を好きな回数行うことができます。
数列 AA に操作を行うことによって得られる数列のうち、各要素の和の最大値を求めてください。

[操作]
整数 ii (0iN1)(0 \leq i \leq N-1 ) を選び、AiA_i xorxor A(i+1)modNA_{(i+1) mod N}A(i+1)modNA_{(i+1) mod N} に代入する。

ただし、xorxor は、ビットごとの排他的論理和を表します。

制約

  • 2N1052 \leq N \leq 10^5
  • 1Ai1091 \leq A_i \leq 10^9 (1iN)(1\leq i \leq N)
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられます。

NN
A0A_0 A1A_1 \cdots AN1A_{N-1}

出力

数列 AA に操作を行うことによって得られる数列のうち、各要素の和の最大値を出力してください。

サンプル

入力1
3
1 2 3
出力1
8

まず、 i=0i=0 として操作を行うと、A0A_0 xor{xor} A1A_{1} の値を A1A_1 に代入することになり、A=(1,3,3)A=(1,3,3) となります。
次に、 i=2i=2 として操作を行うと、A2A_2 xor{xor} A0A_{0} の値を A0A_0 に代入することになり、A=(2,3,3)A=(2,3,3) となります。
このとき、AA の各要素の和は 88 となり、これが最大です。


入力2
2
1 1
出力2
2

入力3
4
2 3 5 7
出力3
25

提出


Go (1.21)