#include<iostream>
#include<cstdio>
#define N 100000
#define M 55
using namespace std;
const int inf=(int)(1e9);
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
struct reads
{
int num,data;
};
int n,q,a[N+1];
struct rds
{
reads dque[M+1];
int top,ans;
};
rds cs;
rds new_node(int x)
{
if (x==inf) cs.dque[cs.top=1]=(reads){x,0},cs.ans=0;
else cs.dque[cs.top=1]=(reads){x,1},cs.ans=x;
return cs;
}
reads dque[M+1];
int rst,top;
void push(reads x)
{
int d;
reads ds;
if (dque[top].num==x.num) dque[top].data+=x.data;
else if (top>=2&&min(dque[top-1].num,x.num)>dque[top].num)
{
d=min(dque[top-1].num,x.num)-dque[top].num;
if (d<=30&&(!(dque[top].data&((1<<d)-1)))) ds=(reads){dque[top].num+d,dque[top].data>>d},top--,push(ds),push(x);
else
{
rst=max(rst,dque[top].num+(31^__builtin_clz(dque[top].data)));
d=dque[top-1].num-dque[top].num;
if (d<=30) dque[top-1].data+=(dque[top].data>>d);
d=x.num-dque[top].num;
if (d<=30) x.data+=(dque[top].data>>d);
ds=dque[top-1],top-=2,push(ds),push((reads){inf,0}),push(x);
}
}
else dque[++top]=x;
return;
}
rds operator + (rds a,rds b)
{
rst=0,top=a.top,a.ans=max(a.ans,b.ans);
for (int i=1;i<=top;++i) dque[i]=a.dque[i];
for (int i=1;i<=b.top;++i) push(b.dque[i]);
a.top=top;
for (int i=1;i<=a.top;++i) a.dque[i]=dque[i];
a.ans=max(a.ans,rst);
return a;
}
struct seg
{
struct node
{
int l,r;
rds data;
};
node tree[(N<<2)+1];
void push_up(int k)
{
tree[k].data=tree[k<<1].data+tree[k<<1|1].data;
return;
}
void build(int k,int l,int r)
{
tree[k].l=l,tree[k].r=r;
if (l==r)
{
tree[k].data=new_node(a[l]);
return;
}
int mid=(l+r)>>1;
build(k<<1,l,mid),build(k<<1|1,mid+1,r),push_up(k);
return;
}
void add(int k,int x,int d)
{
if (tree[k].l==tree[k].r)
{
tree[k].data=new_node(d);
return;
}
int mid=(tree[k].l+tree[k].r)>>1;
if (x<=mid) add(k<<1,x,d);
else add(k<<1|1,x,d);
push_up(k);
return;
}
rds query(int k,int l,int r)
{
if (tree[k].l==l&&tree[k].r==r) return tree[k].data;
int mid=(tree[k].l+tree[k].r)>>1;
if (r<=mid) return query(k<<1,l,r);
else if (l>=mid+1) return query(k<<1|1,l,r);
else return query(k<<1,l,mid)+query(k<<1|1,mid+1,r);
}
};
seg T;
void prepare_game(vector<int>A)
{
n=A.size();
for (int i=1;i<=n;++i) a[i]=A[i-1];
T.build(1,1,n);
return;
}
int play_game(int l,int r)
{
l++,r++;
return (new_node(inf)+T.query(1,l,r)+new_node(inf)).ans;
}
void update_game(int p,int v)
{
p++,T.add(1,p,v);
return;
}