Cyclic Shift and Bitwise Maximum Sum

Given an array \(\{a_i\}_{0 \le i < 2^n}\) of length \(2^n\), you are allowed to perform an arbitrary number of cyclic shifts on the array. A cyclic shift transforms an array \(x\) of length \(m\) into a new array \(x'\) defined as

[ x'i = \begin{cases} x{i-1} & \text{if } i \neq 0,\ x_{m-1} & \text{if } i = 0. \end{cases} ]

Your task is to choose an optimal cyclic shift to maximize the value of one of the following sums:

[ S_{\oplus} = \sum_{i=0}^{2^n-1} \Bigl(a_i \oplus i\Bigr),\quad S_{&} = \sum_{i=0}^{2^n-1} \Bigl(a_i & i\Bigr),\quad S_{\mid} = \sum_{i=0}^{2^n-1} \Bigl(a_i \mid i\Bigr), ]

Here, \(\oplus\), \(\&\), and \(\mid\) denote the bitwise XOR, AND, and OR operations respectively. In other words, if you denote by \(f(k)\) the result after cyclic shifting the array by \(k\) positions (with \(0 \le k < 2^n\)), then you need to compute

[ \max_{0 \le k < 2^n} ; \max \Bigl{ \sum_{i=0}^{2^n-1} \left(a_{(i-k) \bmod 2^n} \oplus i\right), ; \sum_{i=0}^{2^n-1} \left(a_{(i-k) \bmod 2^n} & i\right), ; \sum_{i=0}^{2^n-1} \left(a_{(i-k) \bmod 2^n} \mid i\right) \Bigr}. ]

Input: The first line contains a non-negative integer \(n\). The second line contains \(2^n\) non-negative integers representing the array \(a_i\).

Output: Output a single integer representing the maximum possible value obtainable with an optimal cyclic shift and choosing the best of the three bitwise operation sums.

inputFormat

The first line contains an integer \(n\) (where the length of the array is \(2^n\)). The second line contains \(2^n\) space-separated non-negative integers \(a_i\).

outputFormat

Output a single integer: the maximum value produced by optimally performing a cyclic shift and then taking the best of the three sums \(S_{\oplus}\), \(S_{\&}\), and \(S_{\mid}\).

sample

1
1 0

2