The year is 2022. Red Dragon - the latest spacecraft launched by SpaceX - is already on its way towards Mars. Its main objective is collecting and analyzing Martian soil.
The surface of Mars is seen as a linear array of N consecutive coordinates. Each coordinate i (1 ≤ i ≤ N) has associated some integer value vi describing how interesting that portion of soil appears to be, according to engineers' estimates.
The mission description is, as follows:
- Instead of landing, the capsule hovers at a safe distance.
- Two rovers are launched from it. Each of them lands at some coordinate on the planet, denoted by r1 and r2, respectively.
- Each rover collects information about the piece of soil underneath it. The total value gained is equal to vr1 + vr2.
- Afterwards, the rovers need to meet in order to share and send back their pieces of information. The value lost through fuel consumption is equal to floor(log2 (r2 - r1)).
Your goal is to choose where to place the rovers such that the mission is as successful as possible. Formally, you need to maximize the expression vr1 + vr2 - floor(log2 (r2 - r1)).
Input
The first line of input contains a single integer N.
The second line of input contains N integer values: v1, v2, …, vN.
Output
A single integer: the maximum value of the given expression.
Restrictions
- 1 < N ≤ 105
- -230 ≤ vi ≤ 230
- r1 < r2
Sample
Input | Output |
---|---|
5 5 6 -9 1 10 | 15 |