#include <bits/stdc++.h>
#define f first
#define s second
#define ent '\n'

using namespace std;
typedef long long ll;

int get(deque<pair<int, int>> dq){
    int ans = 0;
    for(int i=0;i+1<dq.size();i++){
        if(dq[i].f > dq[i+1].f){
            break;
        }
        dq[i+1].s += (dq[i].s >> (dq[i+1].f - dq[i].f));
    }
    for(int i=dq.size()-1;i>=1;i--){
        if(dq[i].f > dq[i-1].f){
            continue;
        }
        dq[i-1].s += (dq[i].s >> (dq[i-1].f - dq[i].f));
    }
    for(auto [x, y]:dq){
        while(y > 1){
            x++;
            y /= 2;
        }
        ans = max(ans, x);
    }
    return ans;
}

struct asd{
    deque<pair<int, int>> pref, suff;

    bool same = 1;
    int mx = 0;

    asd(){
        pref.clear(), suff.clear();
        same = 1;
        mx = 0;
    }

    asd(int x){
        pref = suff = {{x, 1}};
        same = 1;
        mx = x;
    }

    void insert(pair<int, int> T){
        auto [x, c] = T;
        if(suff.size() && suff.back().f == x){
            suff[suff.size()-1].s += c;
            if(same){
                pref[pref.size()-1].s += c;
            }
            return;
        }
        bool f = 0;
        while(suff.size() > 1 && suff[suff.size()-2].f > suff.back().f && suff.back().f < x){
            if(suff.back().s % 2 == 0){
                f = 1;
                auto [x, y] = suff.back();
                suff.pop_back();
                if(x+1 == suff.back().f){
                    suff.back().s += y/2;
                }
                else{
                    suff.push_back({x+1, y / 2});
                }
                if(same){
                    pref.pop_back();
                    if(x + 1 == pref.back().f){
                        pref.back().s += y/2;
                    }
                    else{
                        pref.push_back({x+1, y / 2});
                    }
                }
                continue;
            }
            if(same){
                same = 0;
                auto [x, y] = pref.back();
                pref.pop_back();
                if(pref.size() && pref.back().f == x+1){
                    pref.back().s += y / 2;
                }
                else{
                    if(y > 1) pref.push_back({x+1, y/2});
                }
                pref.push_back({x, 1});
                mx = max(mx, get(pref));
            }
            while(suff.size() > 1){
                suff.pop_front();
            }
            int v = x;
            auto [x, y] = suff.back();
            suff.pop_back();
            suff.push_back({x, 1});
            if(y > 1){
                suff.push_back({x+1, y / 2});
            }
            if(suff.back().f == v){
                suff.back().s += c;
            }
            else{
                suff.push_back({v, c});
            }
            mx = max(mx, get(suff));
            return;
        }


        if(suff.size()  && suff.back().f == x){
            suff[suff.size()-1].s += c;
            if(same){
                pref[pref.size()-1].s += c;
            }
            if(f){
                mx = max({mx, get(suff), get(pref)});
            }
            return;
        }

        suff.push_back({x, c});
        if(same){
            pref.push_back({x, c});
        }
        if(f){
            mx = max({mx, get(suff), get(pref)});
        }
        return;
    }

    asd operator +(asd x){
        asd ans;
        ans.suff = suff;
        ans.same = same;
        ans.pref = pref;
        ans.mx = max(mx, x.mx);
        for(auto y:x.pref){
            ans.insert(y);
        }
        ans.mx = max(ans.mx, get(ans.suff));
        if(!x.same) {
            ans.same = 0;
            ans.suff = x.suff;
        }
        ans.mx = max(ans.mx, get(ans.pref));
        ans.mx = max(ans.mx, get(ans.suff));
        return ans;
    }
} t[400002];

int a[100020];
int n, m, k;

void build(int v,int tl,int tr){
    if(tl == tr){
        t[v] = asd(a[tl]);
    }
    else{
        int mid = tl + tr >> 1;
        build(v*2, tl, mid);
        build(v*2+1, mid+1, tr);
        t[v] = t[v*2] + t[v*2+1];
    }
}

void upd(int v, int tl, int tr, int pos, int x){
    if(tl == tr){
        t[v] = asd(x);
    }
    else{
        int mid = tl + tr >> 1;
        if(pos <= mid){
            upd(v*2, tl, mid, pos, x);
        }
        else{
            upd(v*2+1, mid+1, tr, pos, x);
        }
        t[v] = t[v*2] + t[v*2+1];
    }
}

asd get(int v, int tl, int tr, int l, int r){
    if(tl > r || l > tr){
        return t[0];
    }
    if(tl >= l && tr <= r){
        return t[v];
    }
    int mid = tl + tr >> 1;
    return get(v*2, tl, mid, l, r) + get(v*2+1, mid+1, tr, l, r);
}

void prepare_game(vector<int> A) {
    n = A.size();
    for(int i=0;i<n;i++){
        a[i+1] = A[i];
    }
    build(1, 1, n);
}

int play_game(int l, int r) {
    l++, r++;
    return get(1, 1, n, l, r).mx;
}

void update_game(int p, int v) {
    p++;
    upd(1, 1, n, p, v);
}