// 私は猫です

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define cmh(sjy) while(sjy--)
#define lowbit(x) (x&(-x))
#define HH printf("\n")
#define eb emplace_back
#define poly vector<int>
#define SZ(x) ((int)x.size())
using namespace std;
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=500005;
int n,a[maxn];
#define ls (o<<1)
#define rs (o<<1|1)
#define vii vector<pii>
struct node{
	vii vec; int ans;
}t[maxn<<2];
int qmax(vii o){
	if(o.empty())return 0;
	int res=0,mx=0,ans=0;
	for(int i=1;i<o.size();++i)if(o[i].fi>o[mx].fi)mx=i;
	res=o[mx].se;
	pii w={0,0};
	for(int i=0;i<mx;++i){
		w.se=(w.se>>(o[i].fi-w.fi))+o[i].se;
		w.fi=o[i].fi;
	}
	res+=w.se>>(o[mx].fi-w.fi);
	w={0,0};
	for(int i=o.size()-1;i>mx;--i){
		w.se=(w.se>>(o[i].fi-w.fi))+o[i].se;
		w.fi=o[i].fi;
	}
	res+=w.se>>(o[mx].fi-w.fi);
	ans=o[mx].fi;//printf("?%d %d\n",res,ans);
	while(res>1)++ans,res>>=1;
	return ans;
}
node merge(node x,node y){
	node res;
	res.vec.clear(),res.ans=max(x.ans,y.ans);
	auto chk=[&](pii x,pii y){
		if(x.fi>0&&y.fi>0&&x.fi<y.fi)return 1;
		return 0;
	};
	vii tmp=x.vec;
	for(pii i:y.vec){
		for(;SZ(tmp)>1&&chk(tmp.back(),i);){
			pii u=tmp.back(); tmp.pop_back();
			if(!chk(u,tmp.back())){ tmp.push_back(u); break; }
			const int d=min(tmp.back().fi,i.fi)-u.fi;
			if(u.se&((1<<d)-1)){
				tmp.push_back(mkp(u.fi+d,u.se>>d));
				tmp.push_back(mkp(0,0));
				tmp.push_back(mkp(u.fi+d,u.se>>d));
				break;
			}else{
				if(u.fi==tmp.back().fi+d)tmp.back().se+=(u.se>>d);
				else tmp.push_back(mkp(u.fi+d,u.se>>d));
			}
		}
		if(i.fi==tmp.back().fi)tmp.back().se+=i.se;
		else tmp.push_back(i);
	}
	const int siz=SZ(tmp);
	int p=0;
	F(i,0,siz-1){
		res.vec.push_back(tmp[i]);
		if(tmp[i].fi>0)continue;
		if(p){
			vii qaq;
			res.vec.pop_back();
			for(;SZ(res.vec)>p;res.vec.pop_back())qaq.push_back(res.vec.back());
			chkmax(res.ans,qmax(qaq));
		}
		p=SZ(res.vec);
	}
	return res;
}
void build(int o,int l,int r){
	if(l==r)return t[o].vec={{a[l],1}},t[o].ans=a[l],void();
	int mid=(l+r)>>1; build(ls,l,mid),build(rs,mid+1,r);
	t[o]=merge(t[ls],t[rs]);
}
void update(int o,int l,int r,int pos,int val){
	if(l==r)return t[o].vec={{val,1}},t[o].ans=val,void();
	int mid=(l+r)>>1;
	(pos<=mid)?update(ls,l,mid,pos,val):update(rs,mid+1,r,pos,val);
	t[o]=merge(t[ls],t[rs]);
}
node query(int o,int l,int r,int ql,int qr){
	if(ql<=l&&qr>=r)return t[o];
	int mid=(l+r)>>1;
	if(qr<=mid)return query(ls,l,mid,ql,qr);
	if(ql>mid)return query(rs,mid+1,r,ql,qr);
	return merge(query(ls,l,mid,ql,qr),query(rs,mid+1,r,ql,qr));
}
void prepare_game(std::vector<int> A){
	n=A.size();
	F(i,0,n-1)a[i]=A[i];
	build(1,0,n-1);
}
int play_game(int l, int r){
	node tmp=query(1,0,n-1,l,r);
	vii qaq;
	int ans=tmp.ans;
	for(pii i:tmp.vec){
		if(i.fi>0)qaq.push_back(i);
		else chkmax(ans,qmax(qaq)),qaq.clear();
	}
	chkmax(ans,qmax(qaq));
	return ans;
}
void update_game(int p, int v){
	update(1,0,n-1,p,v);
}
signed main(){
	int n;cin>>n;
	vector<int>a;
	F(i,1,n){ int x; cin>>x; a.push_back(x); }
	prepare_game(a);
	int q;cin>>q;
	F(_,1,q){
		int op,x,y;cin>>op>>x>>y;
		if(op==1)cout<<play_game(x,y)<<endl;
		else update_game(x,y);
	}
}

/usr/bin/ld: /tmp/cc4AaHvp.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/ccwZXv6r.o:implementer.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status