#include <bits/stdc++.h>
using namespace std;

int n,m,ans,score[500002];

struct node{
	int maxl,maxr,sum,l,r,val;
}a[2000002];

void pushup(int num) {
	a[num].maxl=max(a[num*2].maxl,a[num*2].sum+a[num*2+1].maxl);
	a[num].maxr=max(a[num*2+1].maxr,a[num*2+1].sum+a[num*2].maxr);
	a[num].sum=a[num*2].sum+a[num*2+1].sum;
	a[num].val=max(max(a[num*2].val,a[num*2+1].val),a[num*2].maxr+a[num*2+1].maxl);
	a[num].val=max(max(a[num*2].l,a[num*2+1].r),a[num].val);
}

void build(int num,int ll,int rr) {
	a[num].l=ll;
	a[num].r=rr;
	if(ll==rr) {
		a[num].val=a[num].maxl=a[num].maxr=a[num].sum=score[ll];
		return ;
	}
	int mid=(ll+rr)>>1;
	build(num*2,ll,mid);
	build(num*2+1,mid+1,rr);
	pushup(num);
}

void update(int num,int pos,int tmp) {
	if(a[num].l==a[num].r) {
		a[num].val=a[num].maxl=a[num].maxr=a[num].sum=tmp;
		return ;
	}
	if(a[num*2].r>=pos && a[num*2].l<=pos) update(num*2,pos,tmp);
	if(a[num*2+1].r>=pos && a[num*2+1].l<=pos) update(num*2+1,pos,tmp);
	pushup(num);
}

node query(int num,int ll,int rr) {
	if(a[num].l>=ll && a[num].r<=rr) return a[num];
	int mid=(a[num].l+a[num].r)>>1;
	if(rr<=mid) return query(num*2,ll,rr);
	else if(ll>mid) return query(num*2+1,ll,rr);
	else {
		node x;
		node x1=query(num*2,ll,mid),x2=query(num*2+1,mid+1,rr);
		x.maxl=max(x1.maxl,x1.sum+x2.maxl);
		x.maxr=max(x1.maxr+x2.sum,x2.maxr);
		x.sum=x1.sum+x2.sum;
		x.val=max(max(x1.val,x2.val),x1.maxr+x2.maxl);
		return x;
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&score[i]);
	build(1,1,n);
	for(int i=1;i<=m;i++) {
		int k,x,y;
		cin>>k>>x>>y;
		if(k==1) {
			if(x>y) swap(x,y);
			else cout<<query(1,x,y).val<<endl;
		} else update(1,x,y);
	}
	return 0;
}