#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,ll y,int p=mod){
	int ans=1;y%=(p-1);
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

template<typename T>void cmax(T &x,T v){x=max(x,v);}
template<typename T>void cmin(T &x,T v){x=min(x,v);}

const int N=1e5+5;
struct Node{
	vector<pair<int,int> >L,R;
	int mx;bool sep;
};

void Rec(vector<pair<int,int> >&A){
	vector<pair<int,int> >B;
	for(int i=0;i<A.size();i++){
		int j=i;int cnt=A[i].se;
		while(j+1<A.size()&&A[j+1].fi==A[i].fi)cnt+=A[j+1].se,j++;
		B.emplace_back(mk(A[i].fi,cnt)),i=j;
	}
	A=B;
}
int Lg[N];
int getans(int x,int y){
	return x+Lg[y];
}
int calc(vector<pair<int,int> >vals){
	if(vals.empty())return 0;
	Rec(vals);
	while(1){
		int mx=0,mn=1e9;
		// cout<<"vals = ";for(auto [v,c]:vals)cout<<"("<<v<<","<<c<<") ";puts("");
		for(auto [v,c]:vals)if(v!=-1)cmax(mx,v),cmin(mn,v);
		// cout<<"mx = "<<mx<<" mn = "<<mn<<endl;
		if(mx==mn)break;
		vector<pair<int,int> >to;
		for(auto [v,c]:vals){
			if(v!=mn){
				to.emplace_back(mk(v,c));
				continue;
			}
			if(c%2==0)to.emplace_back(mk(v+1,c/2));
			else{
				if(c-1>0)to.emplace_back(mk(v+1,(c-1)/2));
				to.emplace_back(mk(-1,1));
				if(c-1>0)to.emplace_back(mk(v+1,(c-1)/2));
			}
		}
		// cout<<"to = ";for(auto [v,c]:to)cout<<"("<<v<<","<<c<<") ";puts("");
		Rec(to);
		// cout<<" -> to = ";for(auto [v,c]:to)cout<<"("<<v<<","<<c<<") ";puts("");
		vals=to;
	}
	int cc=0,vv=0;
	for(auto [v,c]:vals)if(v!=-1)cmax(cc,c),vv=v;

	return getans(vv,cc);
}

const int INF=1e9;
int del_sep(vector<pair<int,int> >&A){
	int pl=INF,pr=-1;
	for(int i=0;i<A.size();i++)if(A[i].fi==-1)cmin(pl,i),cmax(pr,i);
	if(pr==-1||pl==pr)return 0;
	vector<pair<int,int> >B,C;
	for(int i=0;i<=pl;i++)C.emplace_back(A[i]);
	for(int i=pl+1;i<pr;i++)B.emplace_back(A[i]);
	for(int i=pr+1;i<A.size();i++)C.emplace_back(A[i]);
	A=C;
	return calc(B);
}

int vc(int x){return x==-1?INF:x;}
int Simp(vector<pair<int,int> >&A){
	Rec(A);
	int res=0;
	while(1){
		int p=-1;
		for(int i=1;i+1<A.size();i++)if(A[i].fi!=-1){
			if(A[i].fi<min(vc(A[i-1].fi),vc(A[i+1].fi))){p=i;break;}
		}
		if(p==-1)break;
		if(A[p].se%2==0)A[p].fi++,A[p].se/=2,Rec(A);
		else{
			auto [v,c]=A[p];v++,c=(c-1)/2;
			A[p].fi=-1,A[p].se=1;
			if(c>=1){
				auto it=A.begin()+p;
				A.insert(it,mk(v,c));
				it=A.begin()+p+2;
				A.insert(it,mk(v,c));
			}
			cmax(res,del_sep(A));
			Rec(A);
		}
	}
	return res;
}

void print(Node A){
	cout<<"mx = "<<A.mx<<" sep = "<<A.sep<<endl;
	cout<<"L = ";for(auto [v,c]:A.L)cout<<"("<<v<<","<<c<<") ";puts("");
	cout<<"R = ";for(auto [v,c]:A.R)cout<<"("<<v<<","<<c<<") ";puts("");
}

const bool DBG=0;
const bool Test_time=0;
double At=0,Bt=0,Ct=0,Dt=0,Et=0;
Node op(Node lc,Node rc){
	Node res;
	if(DBG){
		cout<<"=========== Merge ===========\n";
		puts("lc : ");
		print(lc);
		puts("rc : ");
		print(rc);
	}
	res.mx=max(lc.mx,rc.mx);
	res.sep=(lc.sep|rc.sep);
	if(lc.sep&&rc.sep){
		if(Test_time)At-=clock();
		vector<pair<int,int> >nw;
		for(auto A:lc.R)nw.emplace_back(A);
		for(auto A:rc.L)nw.emplace_back(A);
		cmax(res.mx,calc(nw));
		res.L=lc.L,res.R=rc.R;
		if(Test_time)At+=clock();
	}
	else if(lc.sep){
		if(Test_time)Bt-=clock();
		res.L=lc.L;
		vector<pair<int,int> >W;
		W.emplace_back(mk(-1,1));
		for(auto A:lc.R)W.emplace_back(A);
		for(auto A:rc.L)W.emplace_back(A);
		cmax(res.mx,Simp(W));
		if(W[0].fi==-1)W.erase(W.begin());
		res.R=W;
		if(Test_time)Bt+=clock();
	}
	else if(rc.sep){
		if(Test_time)Ct-=clock();
		res.R=rc.R;
		vector<pair<int,int> >W;
		W=lc.L;
		for(auto A:rc.L)W.emplace_back(A);
		W.emplace_back(mk(-1,1));
		cmax(res.mx,Simp(W));
		if(W.back().fi==-1)W.pop_back();
		res.L=W;
		if(Test_time)Ct+=clock();
	}
	else{
		if(Test_time)Dt-=clock();
		vector<pair<int,int> >W;
		W=lc.L;
		for(auto A:lc.R)W.emplace_back(A);
		for(auto A:rc.L)W.emplace_back(A);
		for(auto A:rc.R)W.emplace_back(A);
		cmax(res.mx,Simp(W));int p=-1;
		for(int i=0;i<W.size();i++)if(W[i].fi==-1){p=i;break;}
		if(p==-1)res.sep=0,res.L=W;
		else{
			res.sep=1;
			for(int i=0;i<p;i++)res.L.emplace_back(W[i]);
			for(int i=p+1;i<W.size();i++)res.R.emplace_back(W[i]);
		}
		if(Test_time)Dt+=clock();
	}
	// Et-=clock();
	// cmax(res.mx,calc(res.L)),cmax(res.mx,calc(res.R));
	// for(auto [v,c]:res.L)cmax(res.mx,getans(v,c));
	// for(auto [v,c]:res.R)cmax(res.mx,getans(v,c));
	// Et+=clock();
	if(DBG){
		cout<<"res : \n";
		print(res);
	}
	return res;
}

int a[N],n;
struct sgt{
	Node d[N<<2];
	#define ls(p) (p<<1)
	#define rs(p) (p<<1|1)
	void pushup(int p){d[p]=op(d[ls(p)],d[rs(p)]);}
	void build(int l,int r,int p){
		if(l==r){d[p].sep=0,d[p].L.emplace_back(mk(a[l],1)),d[p].mx=a[l];return ;}
		int mid=(l+r)>>1;build(l,mid,ls(p)),build(mid+1,r,rs(p)),pushup(p);
	}
	void modify(int x,int v,int ql,int qr,int p){
		if(ql==qr)return d[p].sep=0,d[p].L[0]=mk(v,1),d[p].mx=v,a[x]=v,void();
		int mid=(ql+qr)>>1;
		if(x<=mid)modify(x,v,ql,mid,ls(p));
		else modify(x,v,mid+1,qr,rs(p));
		pushup(p);
	}
	Node query(int l,int r,int ql,int qr,int p){
		if(l<=ql&&qr<=r)return d[p];
		int mid=(ql+qr)>>1;
		if(l>mid)return query(l,r,mid+1,qr,rs(p));
		if(r<=mid)return query(l,r,ql,mid,ls(p));
		return op(query(l,r,ql,mid,ls(p)),query(l,r,mid+1,qr,rs(p)));
	}
	#undef ls
	#undef rs
}T;

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

int play_game(int l,int r){
	l++,r++;
	auto W=T.query(l,r,1,n,1);
	return max({W.mx,calc(W.L),calc(W.R)});
}

void update_game(int p,int v){
	p++;
	T.modify(p,v,1,n,1);
}

double St;

#ifndef ONLINE_JUDGE
signed main(void){

	if(Test_time)St=clock();
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=2;i<=n;i++)Lg[i]=Lg[i>>1]+1;
	T.build(1,n,1);
	int q=read();
	for(int i=1;i<=q;i++){
		int op=read(),x=read(),y=read();
		if(op==1)cout<<play_game(x,y)<<'\n';
		else update_game(x,y);
	}
	if(Test_time)cerr<<"Time = "<<clock()-St<<"ms\n";
	if(Test_time)cerr<<"At,Bt,Ct,Dt,Et = "<<At<<" "<<Bt<<" "<<Ct<<" "<<Dt<<" "<<Et<<endl;

	return 0;
}
#endif