#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=2e5+1;
int n,q;
ll a[N];
typedef pair<ll,ll> pll;
pll in[524288];
pll f(int x){
	if(a[x]==a[x+1]) return {0LL,(ll)2e9};
	if(a[x]<a[x+1]) return {0LL,(a[x]+a[x+1])/2};
	else return {(a[x]+a[x+1]+1)/2,(ll)2e9};
}
pll g(pll x,pll y){
	return {max(x.fi,y.fi),min(x.se,y.se)};
}
void build(int id,int l,int r){
	if(l==r){
		in[id]=f(l);return;
	}
	int mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	in[id]=g(in[id*2],in[id*2+1]);
}
void upd(int id,int l,int r,int p){
	if(l==r){
		in[id]=f(l);return;
	}
	int mid=(l+r)/2;
	if(p<=mid) upd(id*2,l,mid,p);
	else upd(id*2+1,mid+1,r,p);
	in[id]=g(in[id*2],in[id*2+1]);
}
pll qry(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return {0LL,(ll)2e9};
	if(ql<=l && r<=qr) return in[id];
	int mid=(l+r)/2;
	return g(qry(id*2,l,mid,ql,qr),qry(id*2+1,mid+1,r,ql,qr));
}
void flow(int id,int l,int r){
	cout << id << ' ' << l << ' ' << r << ' ' << in[id].fi << ' ' << in[id].se << endl;
	if(l==r) return;
	int mid=(l+r)/2;
	flow(id*2,l,mid);
	flow(id*2+1,mid+1,r);
}
void solve(){
	cin >> n >> q;
	for(int i=1; i<=n ;i++) cin >> a[i];
	build(1,1,n-1);
	//flow(1,1,n-1);
	for(int i=1; i<=q ;i++){
		int t;cin >> t;
		if(t==1){
			int x;cin >> x;cin >> a[x];
			if(x!=1) upd(1,1,n-1,x-1);
			if(x!=n) upd(1,1,n-1,x);
		}
		else{
			int l,r;cin >> l >> r;
			if(l==r) cout << "0\n";
			else{
				auto fun=qry(1,1,n-1,l,r-1);
				if(fun.fi>fun.se) cout << "-1\n";
				else cout << fun.fi << '\n';
			}
		}
		//flow(1,1,n-1);
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	//int t;cin >> t;while(t--){solve();/*cout << endl;*/}
	solve();
}