// #include"fruitgame.h"
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<tuple>
constexpr int inf{0x3f3f3f3f};
typedef std::tuple<int,std::vector<std::tuple<int,int>>> node;
const node null(0,std::vector<std::tuple<int,int>>({{inf,0}}));
node tr[262145];
inline node merge(const node &x,const node &y) {
    node z(x);
    std::get<0>(z)=std::max(std::get<0>(z),std::get<0>(y));
    const auto append([&](const auto &self,const std::tuple<int,int> &val)->void {
        if(std::get<0>(std::get<1>(z).back())==std::get<0>(val)) {
            std::get<1>(std::get<1>(z).back())+=std::get<1>(val);
            return;
        }
        if(std::get<1>(z).size()>1) {
            const auto a(std::get<1>(z).back());
            const auto b(std::get<1>(z)[std::get<1>(z).size()-2]);
            if(std::get<0>(b)>std::get<0>(a)&&std::get<0>(a)<std::get<0>(val)) {
                const int del(std::min(std::get<0>(b),std::get<0>(val))-std::get<0>(a));
                if(del<=30&&(std::get<1>(a)&(1<<del)-1)==0) {
                    std::get<1>(z).pop_back();
                    self(self,{std::get<0>(a)+del,std::get<1>(a)>>del});
                    self(self,val);
                }
                else {
                    std::get<1>(z).pop_back(),std::get<1>(z).pop_back();
                    std::get<0>(z)=std::max(std::get<0>(z),std::get<0>(a)+std::__lg(std::get<1>(a)));
                    {
                        const int _del(std::get<0>(b)-std::get<0>(a));
                        self(self,{std::get<0>(b),(_del<=30?std::get<1>(a)>>_del:0)+std::get<1>(b)});
                    }
                    self(self,{inf,0});
                    {
                        const int _del(std::get<0>(val)-std::get<0>(a));
                        self(self,{std::get<0>(val),(_del<=30?std::get<1>(a)>>_del:0)+std::get<1>(val)});
                    }
                }
                return;
            }
        }
        std::get<1>(z).emplace_back(val);
    });
    for(const auto v:std::get<1>(y)) {
        append(append,v);
    }
    return z;
}
inline void push_up(const int &p) {
    tr[p]=merge(tr[p<<1],tr[p<<1|1]);
}
void build(const int &p,const int &L,const int &R,const std::vector<int> &A) {
    if(L==R) {
        std::get<0>(tr[p])=0;
        std::get<1>(tr[p]).assign({{A[L-1],1}});
        return;
    }
    const int M(L+R>>1);
    build(p<<1,L,M,A);
    build(p<<1|1,M+1,R,A);
    push_up(p);
}
void modify(const int &p,const int &L,const int &R,const int &x,const int &y) {
    if(L==R) {
        std::get<1>(tr[p]).assign({{y,1}});
        return;
    }
    const int M(L+R>>1);
    if(x<=M) {
        modify(p<<1,L,M,x,y);
    }
    else {
        modify(p<<1|1,M+1,R,x,y);
    }
    push_up(p);
}
node query(const int &p,const int &L,const int &R,const int &l,const int &r) {
    if(l<=L&&r>=R) {
        return tr[p];
    }
    const int M(L+R>>1);
    if(r<=M) {
        return query(p<<1,L,M,l,r);
    }
    if(l>M) {
        return query(p<<1|1,M+1,R,l,r);
    }
    return merge(query(p<<1,L,M,l,r),query(p<<1|1,M+1,R,l,r));
}
int N;
void prepare_game(std::vector<int> A) {
    N=A.size();
    build(1,1,N,A);
}
int play_game(int l,int r) {
    return std::get<0>(merge(null,merge(query(1,1,N,l+1,r+1),null)));
}
void update_game(int p,int v) {
    modify(1,1,N,p+1,v);
}