#include<bits/stdc++.h>
using namespace std;
int n,M;
int t[5000001];
int a[5000001];
int s[5000001],lm[5000001],rm[5000001],m[5000001];
void push(int x){
	s[x]=s[x<<1]+s[x<<1|1];
	lm[x]=max(s[x<<1]+lm[x<<1|1],lm[x<<1]);
	rm[x]=max(rm[x<<1|1],rm[x<<1]+s[x<<1|1]);
	m[x]=max(max(m[x<<1],m[x<<1|1]),lm[x<<1|1]+rm[x<<1]);
	return ;
}
void build(int x,int l,int r){
	if(l==r) {
		s[x]=lm[x]=rm[x]=m[x]=a[x];
		return ;
	}
	int mid=(r+l)>>1;
	build(x<<1,l,mid);
	build(x<<1|1,mid+1,r);
	push(x);
}
void modify(int x,int l,int r,int ql,int qr,int w){
	if(l>=ql&&r<=qr) {
		s[x]=lm[x]=rm[x]=m[x]=w;
		return ;
	}
	int mid=(l+r)>>1;
	if(ql<=mid) modify(x<<1,l,mid,ql,qr,w);
	if(qr>mid) modify(x<<1|1,mid+1,r,ql,qr,w);
	push(x);
}
void search(int x,int l,int r,int ql,int qr){
	if(l>=ql&&r<=qr) return ;
	int mid=(l+r)>>1;
	if(qr<=mid) search(x<<1,l,mid,ql,qr);
	else if(ql>mid) search(x<<1|1,mid+1,r,ql,qr);
	else {
		search(x<<1,l,mid,ql,qr);
		search(x<<1|1,mid+1,r,ql,qr);
		push(x);
	}
}
int main(){
	cin>>n>>M;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=M;i++){
		int k,c,b;
		cin>>k>>c>>b;
		if(k==1){
			if(c>b) swap(c,b);
			search(1,1,n,c,b);
			cout<<m[1]<<endl;
		}
		else modify(1,1,n,c,c,b);
	}	
  	return 0;
}