Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Maximum Subsequence Value

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputRidhiman challenged Ashish to find the maximum valued subsequence of an array $$$a$$$ of size $$$n$$$ consisting of positive integers.

The value of a non-empty subsequence of $$$k$$$ elements of $$$a$$$ is defined as $$$\sum 2^i$$$ over all integers $$$i \ge 0$$$ such that at least $$$\max(1, k - 2)$$$ elements of the subsequence have the $$$i$$$-th bit set in their binary representation (value $$$x$$$ has the $$$i$$$-th bit set in its binary representation if $$$\lfloor \frac{x}{2^i} \rfloor \mod 2$$$ is equal to $$$1$$$).

Recall that $$$b$$$ is a subsequence of $$$a$$$, if $$$b$$$ can be obtained by deleting some(possibly zero) elements from $$$a$$$.

Help Ashish find the maximum value he can get by choosing some subsequence of $$$a$$$.

Input

The first line of the input consists of a single integer $$$n$$$ $$$(1 \le n \le 500)$$$ — the size of $$$a$$$.

The next line consists of $$$n$$$ space-separated integers — the elements of the array $$$(1 \le a_i \le 10^{18})$$$.

Output

Print a single integer — the maximum value Ashish can get by choosing some subsequence of $$$a$$$.

Examples

Input

3 2 1 3

Output

3

Input

3 3 1 4

Output

7

Input

1 1

Output

1

Input

4 7 7 1 1

Output

7

Note

For the first test case, Ashish can pick the subsequence $$$\{{2, 3}\}$$$ of size $$$2$$$. The binary representation of $$$2$$$ is 10 and that of $$$3$$$ is 11. Since $$$\max(k - 2, 1)$$$ is equal to $$$1$$$, the value of the subsequence is $$$2^0 + 2^1$$$ (both $$$2$$$ and $$$3$$$ have $$$1$$$-st bit set in their binary representation and $$$3$$$ has $$$0$$$-th bit set in its binary representation). Note that he could also pick the subsequence $$$\{{3\}}$$$ or $$$\{{2, 1, 3\}}$$$.

For the second test case, Ashish can pick the subsequence $$$\{{3, 4\}}$$$ with value $$$7$$$.

For the third test case, Ashish can pick the subsequence $$$\{{1\}}$$$ with value $$$1$$$.

For the fourth test case, Ashish can pick the subsequence $$$\{{7, 7\}}$$$ with value $$$7$$$.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2021 09:03:30 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|