#include<bits/stdc++.h>
#define ll long long
#define Mid ll mid = (l+r)>>1
using namespace std;
bool st;
const ll N =  5e5 + 20;
ll n, m, a[N], cnt = 0;
struct segtree{
	ll maxv, maxl, maxr, sum;
}tree[N<<3];
ll ls(ll x) {return x<<1;}
ll rs(ll x) {return x<<1|1;}
ll pushup(ll p) {
	tree[p].sum = tree[ls(p)].sum + tree[rs(p)].sum;
	tree[p].maxl = max(tree[ls(p)].maxl, tree[ls(p)].sum+tree[rs(p)].maxl);
	tree[p].maxr = max(tree[rs(p)].maxr, tree[rs(p)].sum+tree[ls(p)].maxr);
	ll k1 = tree[ls(p)].maxr, k2 =  tree[rs(p)].maxl;
	ll K = max(max(k1, k2), k1+k2);
	tree[p].maxv = max(max(tree[ls(p)].maxv, tree[rs(p)].maxv), K);
}

void build(ll p, ll l, ll r) {
	if(l == r) {
		tree[p].maxl = tree[p].maxr = tree[p].maxv = tree[p].sum = a[l];
		return; 
	}
	Mid;
	build(ls(p), l, mid);
	build(rs(p), mid+1, r);
	pushup(p);
	return ;
}
void change(ll p, ll l, ll r, ll x, ll k) {
	Mid;
	if(l == r) {
		tree[p].maxl = tree[p].maxr = tree[p].maxv = tree[p].sum = k;
		return ;
	}
	
	if(x <= mid) change(ls(p), l, mid, x, k);
	if(x >  mid) change(rs(p), mid+1, r, x, k);
	pushup(p);
	return ;
}
segtree query(ll p, ll l, ll r, ll x, ll y) {
	if(x <= l && r <= y) {
		return tree[p];
	}
	Mid;
	segtree A = {0, 0, 0, 0}, B = {0, 0, 0, 0}, C1 = {0, 0, 0, 0};
	bool vis[3];
	if(x <= mid) A = query(ls(p), l, mid, x, y), vis[1] = 1;
	if(y >  mid) B = query(rs(p), mid+1, r, x, y), vis[2] = 1;
	if(vis[1] == 1 && vis[2] == 0) return A;
	else if(vis[1] == 0 && vis[2] == 1) return B;
	else {
	C1.sum = A.sum + B.sum;
	C1.maxl = max(A.maxl, A.sum+B.maxl);
	C1.maxr = max(B.maxr, B.sum+A.maxr);
	ll k1 = A.maxr, k2 =  B.maxl;
	ll K = max(max(k1, k2), k1+k2);
	C1.maxv = max(max(A.maxv, B.maxv), K);
	}
	return C1;
}
bool ed;
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, 1, n);
	for(int i = 1; i <= m; i++) {
		ll op, x, y;
		cin >> op >> x >> y;
		if(op == 2) {
			change(1, 1, n, x, y);
 		}
 		else{
 			if(x>y) swap(x, y);
 			segtree ans = query(1, 1, n, x, y);
			cout << ans.maxv << endl;
		}
	}
	return 0;
}
/*
5 3
1
2
-3
4
5
1 4 5

*/