#include <bits/stdc++.h>
using namespace std;
const int maxn = 500100;
void read(int &x){
	int y=0,w=1;
	char ch=getchar();
	while(ch < '0' || ch > '9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch >= '0' && ch <= '9'){y=y*10+ch-'0';ch=getchar();}
	x=y*w;
}
void write(int x){
	if(x < 0) x=-x,putchar('-');
	if(x > 9) write(x/10);
	putchar(x%10+'0');
}
int n,m;
int a[maxn];
struct node{
	int sum,ans,maxl,maxr;
}t[maxn*4];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;} 
inline void pushup(int p){
	t[p].sum = t[ls(p)].sum + t[rs(p)].sum;
	t[p].maxl = max(t[ls(p)].maxl,t[ls(p)].sum + t[rs(p)].maxl);
	t[p].maxr = max(t[rs(p)].maxr,t[rs(p)].sum + t[ls(p)].maxr);
	t[p].ans = max(t[ls(p)].maxl,t[rs(p)].maxr);
	t[p].ans = max(t[p].ans,t[ls(p)].maxr + t[rs(p)].maxl);
	t[p].ans = max(t[p].ans,t[ls(p)].sum + t[rs(p)].maxl);
	t[p].ans = max(t[p].ans,t[rs(p)].sum + t[ls(p)].maxr);
	t[p].ans = max(t[p].ans,t[ls(p)].ans);//
	t[p].ans = max(t[p].ans,t[rs(p)].ans);//
}
inline void nodeadd(int p,int k){
	t[p].sum += k;
	t[p].maxl += k;
	t[p].maxr += k;
	t[p].ans += k;
}
void build(int p,int l,int r){
	if(l == r){
		nodeadd(p,a[l]);
		return;
	}
	int mid = (l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
	pushup(p);
}
int ask(int p,int l,int r,int nl,int nr){
	int res = INT_MIN;
	if(nl <= l && r <= nr || l == r) return t[p].ans;
	int mid = (l + r) >> 1;
	if(mid < nr) res = max(res,ask(rs(p),mid+1,r,nl,nr));
	if(mid >= nl) res = max(res,ask(ls(p),l,mid,nl,nr));
	return res;
}
void add(int p,int l,int r,int x,int k){
	if(l == r){
		nodeadd(p,k);
		return;
	}
	int mid = (l + r) >> 1;
	if(mid < x) add(rs(p),mid+1,r,x,k);
	if(mid >= x) add(ls(p),l,mid,x,k);
	pushup(p);
}
int main(){
	read(n),read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	build(1,1,n);
	int k,x,y;
	while(m--){
		read(k),read(x),read(y);
		if(k == 1){
			if(x > y) swap(x,y);
			write(ask(1,1,n,x,y)),putchar('\n');
		}
		if(k == 2) add(1,1,n,x,y-a[x]),a[x]=y;
	}
	return 0;
}