//P4513 小白逛公园
//线段树维护区间子段和最大值，单点修改 
//k=1时候，区间查询
//k=2时候，单点修改
/*
	maxx:区间最大值
	maxl:以l为左端点的区间最大值 
	maxr:以r为右端点的区间最大值 
	sum:区间和
	
更新：
 	maxx = max (max(左子maxx，右子maxx), 左子maxr+右子maxl) 
	maxl = max (左子maxl，左子sum+右子maxl)
	maxr = max (右子maxr，右子sum+左子maxr)
	 sum = max (左子sum+右子sum) 
*/
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f
int n, m;
const int maxn = 5e5 + 5;
int a[maxn];
struct node{
	int sum;
	int maxx;//区间最大值 
	int maxl;//以l为左端点的区间最大值 
	int maxr;//以r为右端点的区间最大值 
//	 node(){
//	 	sum = maxx = maxl = maxr = -inf;
//	 }
};
node val[maxn << 2];
node nul;//空区间 

void merge(node &res, const node &l, const node &r){//合并 
	res.sum = l.sum + r.sum;
	res.maxx = max (max (l.maxx,r.maxx), l.maxr+r.maxl);
	res.maxl = max (l.maxl, l.sum + r.maxl);
	res.maxr = max (r.maxr, r.sum + l.maxr);
} 

void pushup(int rt){
	merge(val[rt], val[rt<<1],val[rt<<1|1]);
}

void modify (node &res, int x){//修改 
	res.maxx = x;
	res.maxl = x;
	res.maxr = x;
	res.sum  = x;
}

void build (int rt, int l, int r){
	if (l == r){
		modify(val[rt],a[l]);
//		val[rt] = {a[l],a[l],a[l],a[l]};
		return ;
	}
	int mid = (l+r)>>1;
	build(rt<<1,l,mid);
	build(rt<<1|1,mid+1,r);
	pushup(rt);
}

void update(int rt, int l, int r, int pos, int k){
	if (l==pos && r==pos){
		modify(val[rt], k);
//		val[rt] = {a[l],a[l],a[l],a[l]};
		return ;
	}
	int mid = (l + r)>>1;
	if (pos<=mid){
		update(rt<<1,l,mid,pos,k);
	}else{
		update(rt<<1|1,mid+1,r,pos,k);
	}
	pushup(rt);
}

node query(int rt, int l, int r, int ql, int qr){
	if (qr < l || ql > r){
		return nul;
	}
	if(ql <= l && r <= qr){
		return val[rt];
	}
	int mid = (l+r)>>1;
	node res = nul;
	node tmp = nul;
	merge(res,tmp,query(rt<<1,l,mid,ql,qr));
	tmp = res;
	merge(res,tmp,query(rt<<1|1,mid+1,r,ql,qr));	
	return res;
}

//node query(int rt, int l, int r, int ql, int qr){
//	if(ql <= l && r <= qr){
//		return val[rt];
//	}
//	int mid = (l+r)>>1;
//	if(qr<=mid) return query(rt<<1,l,mid,ql,qr);
//	else if (ql > mid)return query(rt<<1|1,mid+1,r,ql,qr);
//	else{
//		node res = query(rt<<1,l,mid,ql,mid);
//		node tmp = query(rt<<1|1,mid+1,r,mid+1,qr);
//		node ans;
//		merge(ans,res,tmp);
//		return ans;
//	}
//	
//}

int main () {
	nul.sum = -inf;	
	nul.maxx = -inf;
	nul.maxr = -inf;
	nul.maxl = -inf;
	cin >> n >> m;
	for (int i = 1;i <= n; i++){
		cin >> a[i];
	}	
	build (1,1,n);
	while (m--){
		int op, x, y;
		cin >> op >> x >> y;
		if (op == 1){
			if (x > y) swap(x, y);
			node ans = query(1,1,n,x,y);
			cout <<  ans.maxx <<'\n';
		}else{
			update(1,1,n,x,y);
		}
	}
	return 0;
}