Red Dragon

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

InputOutput
5
5 6 -9 1 10
15
Questions?

Sponsors Gold