Chaos

Setting up dominoes and watching them topple has become too boring for Doctor Brown, so he invented a new and more mathematical way to waste time.

A board holds $n$ integers. Doctor Brown repeats the following move:

• He picks three numbers $a$, $b$ and $c$ written on the board and erases them.
• He picks two of those three numbers and computes their average, rounding down when the sum is odd. Call the result $d$.
• He writes $d$ on the board twice.

Suppose the board holds 1, 2 and 4. After erasing all three, Doctor Brown can write two copies of 1 (the average of 1 and 2, rounded down), two copies of 2 (the average of 1 and 4, rounded down), or two copies of 3 (the average of 2 and 4). The process stops once two numbers are left, and those two numbers are always equal.

Marty watched Doctor Brown and thought the moves looked random. Doctor Brown says they were not. He claims he chose every move so that the number left on the board is as large as possible. Marty wrote down the starting numbers. Find the largest value the two remaining numbers can take.

The first line contains one integer $n$ ($3 \le n \le 10^5$), the count of integers written on the board.

The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^9$), the numbers on the board.

Print one integer, the largest possible value of the two numbers left on the board after Doctor Brown finishes.