#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=4e6+10;
const int M=1e3+10;

int n,m;
int w[N];
void init(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>w[i];
	}
}

struct Tree{
	int ls;
	int rs;
	int k;// int sum;
	int ans;
	int al;
	int ar;
}tr[N];
int cnt=0;//节点数量 
void build(int k,int l,int r){
	if(l==r){
		tr[k].k=w[l];
		tr[k].ans=w[l];
		tr[k].al=w[l];
		tr[k].ar=w[l];
		return ;
	}
	int mid=(l+r)/2;
	tr[k].ls=++cnt;
	tr[k].rs=++cnt;
	build(tr[k].ls,l,mid);
	build(tr[k].rs,mid+1,r);
	
	tr[k].k=tr[tr[k].ls].k+tr[tr[k].rs].k;
	tr[k].ans=max(max(tr[tr[k].ls].ans,tr[tr[k].rs].ans),tr[tr[k].ls].ar+tr[tr[k].rs].al);
	tr[k].al=max(tr[tr[k].rs].al,tr[tr[k].ls].al+tr[tr[k].rs].k);
	tr[k].ar=max(tr[tr[k].ls].ar,tr[tr[k].rs].ar+tr[tr[k].ls].k);
}
void change(int k,int l,int r,int y,int x){
	if(l==r){
		tr[k].k=x;
		tr[k].al=x;
		tr[k].ar=x;
		tr[k].ans=x;
		return ;
	}
	int mid=(l+r)/2;
	if(y<=mid){
		change(tr[k].ls,l,mid,y,x);
	}
	if(y>mid){
		change(tr[k].rs,mid+1,r,y,x);
	}
	
	tr[k].k=tr[tr[k].ls].k+tr[tr[k].rs].k;
	tr[k].ans=max(max(tr[tr[k].ls].ans,tr[tr[k].rs].ans),tr[tr[k].ls].ar+tr[tr[k].rs].al);
	tr[k].al=max(tr[tr[k].rs].al,tr[tr[k].ls].al+tr[tr[k].rs].k);
	tr[k].ar=max(tr[tr[k].ls].ar,tr[tr[k].rs].ar+tr[tr[k].ls].k);
}
/*
int num[N];//总和
int al[N];//向左延伸最大值
int ar[N];//向右延伸最大值
int ans[N];//从mid向左右延伸最大值 
*/
int find(int k,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return tr[k].ans;
	}
	int mid=(l+r)/2;
	int ll=-0x7fffffff,rr=-0x7fffffff;
	if(L<=mid){
		ll=find(tr[k].ls,l,mid,L,R);
	}
	if(mid+1<=R){
		rr=find(tr[k].rs,mid+1,r,L,R);
	}
	return max(ll,rr);
}
int main(){
	init();
	build(++cnt,1,n);
	for(int i=1;i<=m;i++){
		int x;
		cin>>x;
		if(x==1){
			int a,b;
			cin>>a>>b;
			if(a>b){
				swap(a,b);
			}
			//cout<<find(a,b);//?
			/*for(int j=1;j<=cnt;j++){
				cout<<tr[j].al<<' ';
			}
			cout<<endl;*/
			cout<<find(1,1,n,a,b)<<endl;
		}
		if(x==2){
			int p,s;
			cin>>p>>s;
			change(1,1,n,p,s);
		}
	}
	return 0;
}