#include<cstdio> #include<bitset> #include<vector> #include<cstring> #include<cmath> #include<cstdlib> #include<ctime> #include<map> #include<set> #include<queue> #include<algorithm> using namespace std; int maxi, N, v[100009]; class RangeMinimumQuery { public: int N; void fix_val (int pos, int val) { dp[0][pos] = val; } void RunIt () { for (int i=2; i<=N; i++) lg[i] = lg[i >> 1] + 1; for (int i=1; (1<<i) <= N; i++) for (int j=1; j + (1 << i) - 1 <= N; j++) dp[i][j] = F (dp[i - 1][j], dp[i - 1][j + (1 << (i - 1))]); } int Query (int x, int y) { int p = lg[y - x + 1]; return F (dp[p][x], dp[p][y - (1 << p) + 1]); } private: bool GL_type; int dp[20][100009], lg[100009]; int F (int x, int y) { if (x > y) return x; return y; } }rmq; int main() { //freopen ("input", "r", stdin); //freopen ("output", "w", stdout); scanf ("%d", &N), rmq.N = N; for (int i=1; i<=N; i++) scanf ("%d", &v[i]), rmq.fix_val (i, v[i]); rmq.RunIt (); for (int i=1; i<=N; i++) for (int k=0; (1<<k) + i <= N; k++) { int st = i + (1 << k), dr = i + (1 << (k + 1)) - 1; if (dr > N) dr = N; int curr = v[i] + rmq.Query (st, dr) - k; if ((i == 1 && k == 0) || curr > maxi) maxi = curr; } printf ("%d\n", maxi); return 0; }