题目描述

给定整数序列 $A$，要构造一个数列 $B$，其中 $B$ 由 $0, 1$ 组成，且 $0$ 的个数等于 $1$ 的个数。

在此前提下，构造一个数列 $B$ 使得 $\sum_{i=2}^n A[i]*(B[i] \otimes B[⌊i/2⌋])$ 最大。输出这个值的最大可能值。

其中，$\otimes$ 表示同或运算。也就是，$1 \otimes 1=1, 0 \otimes 0=1, 1 \otimes 0 = 0, 0 \otimes 1 = 0$。

输入格式

第一行输入一个正整数 $n$。

第二行输入 $n$ 个被空格分开的整数 $A_1, A_2, \dots ,A_n$。

输出格式

一行一个正整数，表示 $\sum_{i=2}^n A[i]*(B[i] \otimes B[⌊i/2⌋])$ 的最大可能值。

样例

样例输入 1

6
14 10 -7 -50 -50 20

样例输出 1

20

样例解释 1

最优的 $B=\{0, 1, 1, 0, 0, 1\}$。

更多样例

见附加文件。

数据范围与提示

对于所有的测试点, 满足 $n$ 为偶数, $n \leq 450,-10^9 \leq A_i \leq 10^9$.

• 对于 $10 \%$ 的数据, 满足 $n \leq 3$
• 对于 $30 \%$ 的数据, 满足 $n \leq 20$
• 对于 $80 \%$ 的数据, 满足 $n \leq 80$