题目描述

给定一个长度为 $n$ 的非负整数序列 $[a_1,\dots,a_n]$，求它的一个子序列 $[a_{i_1},a_{i_2},\dots,a_{i_k}]\ (1\le i_1\lt i_2\lt \dots\lt i_k\le n)$，使得 $\sum_{j=1}^{k-1}(a_{i_j}\operatorname{and} a_{i_{j+1}})$ 最大。你只需要输出这个最大值即可。

这里，$\operatorname{and}$ 是指二进制按位与。

子序列的定义是：从原序列中任意删除若干个（可以是 0 个）数，将剩下的数按原来的相对顺序拼起来，得到的序列。

输入格式

第一行一个正整数 $n$。接下来一行 $n$ 个整数 $a_1\sim a_n$。

输出格式

输出一个整数，为 $\sum_{j=1}^{k-1}(a_{i_j}\operatorname{and} a_{i_{j+1}})$ 的最大值。

样例

样例输入 1

5
1 2 3 1 3

样例输出 1

5

样例 1 解释

一种最优解为：取子序列为 $[a_2,a_3,a_5]$。

样例输入 2

2
1000000000000 987654321234

样例输出 2

965637836800

样例 3,4

见下发文件。

数据范围

所有数据均满足：$1\le n\le 10^{6}$，$0\le a_i\le 10^{12}$。

• 子任务 1（$20$ 分）：$n\le 20$。
• 子任务 2（$25$ 分）：$n\le 5000$。
• 子任务 3（$20$ 分）：$n\le 10^5,a_i\lt 512$。
• 子任务 4（$15$ 分）：$n\le 2\times 10^5$，每个 $a_i$ 都是在 $[0,10^{12}]$ 独立均匀随机生成的。
• 子任务 5（$20$ 分）：无特殊限制。

大数据