← 返回题目列表

Codeforces · 1365/E

E. 最大子序列值

中文机器翻译题面 查看原题

Ridhiman 向 Ashish 提出挑战,要求找出由正整数组成的大小为 $$$n$$$ 的数组 $$$a$$$ 的最大值子序列。

$$$a$$$ 的 $$$k$$$ 元素的非空子序列的值定义为所有整数 $$$i \ge 0$$$ 上的 $$$\sum 2^i$$$,这样子序列的至少 $$$\max(1, k - 2)$$$ 元素在其二进制表示中设置了第 $$$i$$$ 位(值如果 $$$\lfloor \frac{x}{2^i} \rfloor \mod 2$$$ 等于 $$$1$$$,则 $$$x$$$ 在其二进制表示中设置了第 $$$i$$$ 位。

回想一下,$$$b$$$ 是 $$$a$$$ 的子序列,如果 $$$b$$$ 可以通过从 $$$a$$$ 中删除一些(可能为零)元素来获得。

帮助 Ashish 通过选择 $$$a$$$ 的某些子序列来找到他可以获得的最大值。

输入

输入的第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 500)$$$ — $$$a$$$ 的大小。

下一行由 $$$n$$$ 空格分隔的整数组成 - 数组 $$$(1 \le a_i \le 10^{18})$$$ 的元素。

输出

打印单个整数 - Ashish 通过选择 $$$a$$$ 的某些子序列可以获得的最大值。

示例

输入 #1

3
2 1 3

输出 #1

3

输入 #2

3
3 1 4

输出 #2

7

输入 #3

1
1

输出 #3

1

输入#4

4
7 7 1 1

输出#4

7

注意

对于第一个测试用例,Ashish 可以选择大小为 $$$2$$$ 的子序列 $$$\{{2, 3}\}$$$。 $$$2$$$ 的二进制表示形式为 10,$$$3$$$ 的二进制表示形式为 11。由于 $$$\max(k - 2, 1)$$$ 等于 $$$1$$$,因此子序列的值为 $$$2^0 + 2^1$$$($$$2$$$ 和 $$$3$$$ 在其二进制表示形式中都设置了 $$$1$$$-st 位,并且$$$3$$$ 在其二进制表示中设置了 $$$0$$$ 位)。请注意,他还可以选择子序列 $$$\{{3\}}$$$ 或 $$$\{{2, 1, 3\}}$$$。

对于第二个测试用例,Ashish 可以选择子序列 $$$\{{3, 4\}}$$$,其值为 $$$7$$$。

对于第三个测试用例,Ashish 可以选择子序列 $$$\{{1\}}$$$,其值为 $$$1$$$。

对于第四个测试用例,Ashish 可以选择子序列 $$$\{{7, 7\}}$$$,其值为 $$$7$$$。