#include <iostream> #include <algorithm> #include <cstring> #include <cmath> using namespace std; int n; long long v[100100], sol = -4000000100LL; long long rmq[100100][20], put[100100]; inline long long Maxim(int st, int dr) { int lg=dr-st+1; int Exp=put[lg]; int dif=lg-(1<<Exp); return max(rmq[st][Exp],rmq[st+dif][Exp]); } int main() { int i, k, lg, lim, dif; cin >> n; for(i = 1; i <= n; ++i) cin >> v[i]; for(i=1;i<=n;i++) rmq[i][0]=v[i]; for(k=1;(1<<k)<=n;k++) { lim=n-(1<<k)+1; for(i=1;i<=lim;i++) { lg=(1<<(k-1)); rmq[i][k]=max(rmq[i][k-1],rmq[i+lg][k-1]); } } put[1]=0; for(i=2;i<=n;i++) put[i]=put[i/2]+1; for(i = 2; i <= n; ++i) { for(dif = 1; i - dif > 0; dif = (dif << 1)) { sol = max(sol, v[i] + Maxim(max(1, i - (dif << 1) + 1), i - dif) - put[dif]); } } cout << sol << "\n"; return 0; }