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

**has associated some integer value**

`i (1 ≤ i ≤ N)`**describing how interesting that portion of soil appears to be, according to engineers' estimates.**

`v`_{i}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
and`r`_{1}, respectively.`r`_{2} - Each rover collects information about the piece of soil underneath it. The total value gained is equal to
.`v`_{r1}+ v_{r2} - 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(log`_{2}(r_{2}- r_{1}))

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 ** v_{r1} + v_{r2} - floor(log_{2} (r_{2} - r_{1}))**.

### Input

The first line of input contains a single integer ** N**.

The second line of input contains ** N** integer values:

**.**

`v`_{1}, v_{2}, …, v_{N}### Output

A single integer: the maximum value of the given expression.

### Restrictions

`1 < N ≤ 10`^{5}`-2`^{30}≤ v_{i}≤ 2^{30}`r`_{1}< r_{2}

### Sample

Input | Output |
---|---|

55 6 -9 1 10 | 15 |

The solution to this problem comes with a few key observations:

- The value of the logarithm factor will never exceed
, since all valid indices belong to the interval**log N**.`[1, N]` - For a fixed starting index
, the next indices (`P`) can be split into groups, each having a specific value for the logarithm factor. So, in order to maximize the value`P+1, P+2, …, N`, one must take the maximum value among all the groups.**v**_{P}+ v_{Q}- floor(log_{2}(Q - P))

Based on the implementation, time and space complexity may differ. We will provide two different implementations:

### Cosmin Rusu: `O(N * log`_{2} N)

`O(N * log`

_{2}N)This solution has the best time complexity among all the solutions and it uses the RMQ data structure.

1 #include <iostream> 2 #include <string.h> 3 #include <fstream> 4 5 using namespace std; 6 7 const int maxn = 100005; 8 const int maxlg = 18; 9 10 int rmq[maxlg][maxn * 10]; 11 12 int main() { 13 int n; 14 cin >> n; 15 memset(rmq, -0x3f3f3f3f, sizeof(rmq)); 16 for(int i = 1 ; i <= n ; ++ i) 17 cin >> rmq[0][i]; 18 19 for(int i = 1 ; i < maxlg ;++ i) 20 for(int j = 1 ; j <= n ; ++ j) { 21 rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]); 22 } 23 24 long long ans = -0x3f3f3f3f; 25 for(int i = 1 ; i < n ; ++ i) { 26 for(int lg = 0 ; lg < maxlg ; ++ lg) { 27 int st = i + (1 << lg); 28 ans = max(ans, 1LL * rmq[0][i] + rmq[lg][st] - lg); 29 } 30 } 31 cout << ans << '\n'; 32 }

### Petru Trîmbiţaş: **O(N * log**_{2}^{2} N)

**O(N * log**

_{2}^{2}N)Here's the simplest way to do this:

1 #include <iostream> 2 #include <set> 3 #include <cstdio> 4 #define DN 100005 5 using namespace std; 6 7 typedef pair<int,int> per; 8 int n,v[DN],rez=-(1<<30); 9 set<per, greater<per> > s[20]; 10 11 int main() { 12 //freopen("1000.in","r",stdin); 13 cin>>n; 14 for(int i=0; i<n; ++i) cin>>v[i]; 15 for(int i=1; i<n; ++i) { 16 for(int j=1,ind=1; i-j>=0; j<<=1,++ind) { 17 if(s[ind-1].find(make_pair(v[i-j],i-j))!=s[ind-1].end()) s[ind-1].erase(s[ind-1].find(make_pair(v[i-j],i-j))); 18 s[ind].insert(make_pair(v[i-j],i-j)); 19 } 20 for(int j=0; j<20; ++j) if(s[j].size()) rez=max(rez,v[i]+s[j].begin()->first-(j-1)); 21 } 22 cout<<rez; 23 }