#include<bits/stdc++.h>
using namespace std;
const int N = 2 * 1e6 + 10;
int n,m,x,y,a[N];
struct tree{
	int xl,xr,lmax,rmax,d,sum;
}t[4 * N];
void crt(int p,int l,int r){
	t[p].xl = l;
	t[p].xr = r;
	if(l == r){
		t[p].sum = a[l];
		t[p].lmax = a[l];
		t[p].rmax = a[l];
		t[p].d = a[l];
		return ;
	}
	crt(p * 2,l,(l + r) / 2);
	crt(p * 2 + 1,(l + r) / 2 + 1,r);
	t[p].lmax = max(t[p * 2].lmax,t[p * 2].sum + t[p * 2 + 1].lmax);
	t[p].rmax = max(t[p * 2 + 1].lmax,t[p * 2 + 1].sum + t[p * 2].rmax);
	t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
	t[p].d = max(max(t[p * 2].d,t[p * 2 + 1].d),t[p * 2].rmax + t[p * 2 + 1].lmax);
	return ;
}
void ch(int p,int i,int nx){
	if(t[p].xl == t[p].xr){
		t[p].sum = nx;
		t[p].lmax = nx;
		t[p].rmax = nx;
		t[p].d = nx;
		return ;
	}
	int mid = (t[p].xl + t[p].xr) / 2;
	if(i <= mid) ch(p * 2,i,nx);
	else ch(p * 2 + 1,i,nx);
	t[p].lmax = max(t[p * 2].lmax,t[p * 2].sum + t[p * 2 + 1].lmax);
	t[p].rmax = max(t[p * 2 + 1].lmax,t[p * 2 + 1].sum + t[p * 2].rmax);
	t[p].sum = t[p * 2].sum + t[p * 2 + 1].sum;
	t[p].d = max(max(t[p * 2].d,t[p * 2 + 1].d),t[p * 2].rmax + t[p * 2 + 1].lmax);
	return ;
}
tree ask(int p, int l, int r){
    if(l <= t[p].xl && t[p].xr <= r){
        return t[p];
    }
    int mid = (t[p].xl + t[p].xr) / 2;
    if(r <= mid){
        return ask(p * 2, l, r);
    }
	else if(l > mid){
        return ask(p * 2 + 1, l, r);
    }
	else{
        tree left = ask(p * 2, l, mid);
        tree right = ask(p * 2 + 1, mid + 1, r);
        tree res;
        res.sum = left.sum + right.sum;
        res.lmax = max(left.lmax,left.sum + right.lmax);
        res.rmax = max(right.rmax,right.sum + left.rmax);
        res.d = max(max(left.d,right.d),left.rmax + right.lmax);
        return res;
    }
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	for(int i = 1;i <= n;++i){
		cin >> a[i];
	}
	crt(1,1,n);
	while(m--){
		int op;
		cin >> op >> x >> y;
		if(op == 1){
			if(x > y) swap(x,y);
			tree ans = ask(1,x,y);
			cout << ans.d << endl;
		}
		else ch(1,x,y);
	}
	return 0;
}