#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+5;
struct node{
	int l,r,sum,mxl,mxr,mx;
}tree[maxn*4];
int n,m,op,x,y,a[maxn];
void refresh(int now){
	tree[now].mx=max(tree[now*2].mxr+tree[now*2+1].mxl,max(tree[now*2].mx,tree[now*2+1].mx));
	tree[now].mxl=max(tree[now*2].sum+tree[now*2+1].mxl,tree[now*2].mxl);
	tree[now].mxr=max(tree[now*2].mxr+tree[now*2+1].sum,tree[now*2+1].mxr);
	tree[now].sum=tree[now*2].sum+tree[now*2+1].sum;
}
void build(int now,int l,int r){
	tree[now].l=l,tree[now].r=r;
	if(l==r){
		tree[now].mx=a[l];
		tree[now].mxr=a[l];
		tree[now].mxl=a[l];
		tree[now].sum=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(now*2,l,mid);
	build(now*2+1,mid+1,r);
	refresh(now);
}
void change(int i,int d,int num){
	if(tree[i].l==tree[i].r){
		tree[i].mx=num;
		tree[i].mxr=num;
		tree[i].mxl=num;
		tree[i].sum=num;
		return;
	}
	if(tree[i*2].r>=d&&d>=tree[i*2].l)
		change(i*2,d,num);
	if(tree[i*2+1].r>=d&&d>=tree[i*2+1].l)
		change(i*2+1,d,num);
	refresh(i);
}
int search(int i,int l,int r){
	if(tree[i].l>=l&&tree[i].r<=r)
		return tree[i].mx;
	int s=-1e9;
	if(tree[i*2].r>=l){
		s=max(s,search(i*2,l,r));
	}
	if(tree[i*2+1].l<=r){
		s=max(s,search(i*2+1,l,r));
	}
	return s;
}
int main(){
	freopen("P4513_2.in","r",stdin);
	freopen("ans.txt","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	build(1,1,n);
	while(m--){
		scanf("%d%d%d",&op,&x,&y);
		if(op==1){
			if(x>y)swap(x,y);
			printf("%d\n",search(1,x,y));
		}else
			change(1,x,y);
	}
}