#include<iostream>
#include<cstdio>
#include<algorithm>
//#include<cstring>
/*using std::cin;
using std::cout;
using std::endl;*/
//#define int long long
using namespace std;
int v[2000000];
struct segment_tree {
	int l,r;
	int subl,subr,sum;
}t[10000000];
/*long long max(long long a,long long b) {
	return a<b ? b : a;
}
void swap(long long &a,long long &b) {
	long long t;
	t=a;
	a=b;
	b=t;
}*/
void build (int o,int l,int r) {
	//cout<<o<<' '<<l<<' '<<r<<endl;
	t[o].l=l,t[o].r=r;
	int mid=(l+r)>>1;
	if (l==r) {
		t[o].subl=t[o].subr=t[o].sum=v[l];
		return ;
	}
	build(o*2,l,mid);
	build(o*2+1,mid+1,r);
	t[o].subl=max(t[o*2].subl,t[o*2].sum+t[o*2+1].subl);
	t[o].subr=max(t[o*2+1].subr,t[o*2+1].sum+t[o*2].subr);
	t[o].sum=t[o*2].sum+t[o*2+1].sum;
	return ;
}
void maintain (int o) {
	if (t[o].l==t[o].r) {
		t[o].subl=t[o].subr=t[o].sum=v[t[o].l];
		return ;
	}
	t[o].subl=max(t[o*2].subl,t[o*2].sum+t[o*2+1].subl);
	t[o].subr=max(t[o*2+1].subr,t[o*2+1].sum+t[o*2].subr);
	t[o].sum=t[o*2].sum+t[o*2+1].sum;
	return ;
}
void modify (int o,int pos) {
	if (t[o].l==t[o].r) {
		maintain(o);
		return ;
	}
	int mid=(t[o].l+t[o].r)>>1;
	if (pos<=mid) modify(o*2,pos);
	else modify(o*2+1,pos);
	maintain(o);
	return ;
}
int queryl(int o,int l,int r) {
	if (t[o].l==t[o].r) return v[t[o].l];
	int mid=(t[o].l+t[o].r)>>1;
	if (r<=mid) return queryl(o*2,l,r);
	return max(t[o*2].subl,t[o*2].sum+queryl(o*2+1,l,r));
}
    int queryr(int o,int l,int r) {
	if (t[o].l==t[o].r) return v[t[o].l];
	int mid=(t[o].l+t[o].r)>>1;
	if (l>mid) return queryr(o*2+1,l,r);
	return max(t[o*2+1].subr,t[o*2+1].sum+queryr(o*2,l,r));
}
int query (int o,int l,int r) {
	if (t[o].l==t[o].r) return v[t[o].l];
	int mid=(t[o].l+t[o].r)>>1;
	if (r<=mid) return query(o*2,l,r);
	if (l>mid) return query(o*2+1,l,r);
	int ans=-998244353114514;
	ans=max(query(o*2,l,r),query(o*2+1,l,r));
	ans=max(ans,queryr(o*2,l,r)+queryl(o*2+1,l,r));
	return ans;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m;
	cin>>n>>m;
	for (int i=0;i<n;i++) cin>>v[i];
	build(1,0,n-1);
	for (int i=0;i<m;i++) {
		int op;
		cin>>op;
		if (op==1) {
			int l,r;
			cin>>l>>r;
			if (l>r) swap(l,r);
			l--,r--;
			cout<<query(1,l,r)<<endl;
		}
		if (op==2) {
			int pos,x;
			cin>>pos>>x;
			pos--;
			v[pos]=x;
			modify(1,pos);
		}
	}
	return 0;
}