#include <iostream> #include <cmath> #include <vector> #include <array> using namespace std; constexpr int maxniv = 18; class rmq{ int n; vector<array<int, maxniv>> d; public: rmq(const vector<int>& v): n(v.size()), d(n){ for(int i = 0; i < n; ++i){ d[i][0] = v[i]; } for(int niv = 1, step = 1; niv < maxniv; ++niv, step *= 2){ for(int i = 0; i < n; ++i){ d[i][niv] = max(d[i][niv-1], d[min(i+step, n-1)][niv-1]); } } } int operator()(const int a, const int b){ const int dist = b-a+1, niv = log2(dist), step = 1<<niv; return max(d[a][niv], d[b-step+1][niv]); } }; int main(){ int n; cin >> n; vector<int> v(n, 0); for(auto& x : v){ cin >> x; } rmq r(v); long long rez = v[0] + v[1]; for(int niv = 0; niv < maxniv; ++niv){ for(int i = 0, j = (2<<niv)-1; j < n; ++i, ++j){ rez = max(rez, (long long)v[i] + (long long)r(i+1, j) - niv); } } cout << rez << endl; return 0; }