// P4513
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 6e5 + 5;
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)

int n,m,ans = -1e8,ans2=0;
int a[MAXN];
struct node{
    int v,maxv,maxl,maxr;
}s[MAXN<<2];

void push_up(int p){
    s[p].v = s[ls(p)].v + s[rs(p)].v;
    s[p].maxl = max(s[ls(p)].maxl, s[ls(p)].v + s[rs(p)].maxl);
	s[p].maxr = max(s[rs(p)].maxr, s[rs(p)].v+s[ls(p)].maxr);
    s[p].maxv = max({s[p].maxl,s[p].maxr,s[ls(p)].maxr+s[rs(p)].maxl});
}

void build(int p,int l,int r){
    if (l == r){
        s[p].v = a[l];
        s[p].maxv = s[p].maxl = s[p].maxr = a[l];
      	return ;
    }
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    push_up(p);
}

void update(int p,int l,int r,int P,int S){
	if (l == r){
		s[p].v = S;
		s[p].maxv = s[p].maxl = s[p].maxr = S;
		return ;
	}
	if (P <= (l+r)>>1){
		update(ls(p),1,mid,P,S);
	}
	else{
		update(rs(p),mid+1,r,P,S);
	}
	push_up(p);
}

void ask(int p,int l,int r,int L,int R){
	if (l > R || r < L){
		return ;
	}
	if (l >= L && r <= R){
		// cout << "ok";
		ans = max({ans,ans2+s[p].maxl ,s[p].maxv});
		ans2 = max(ans2+s[p].v,s[p].maxr);
		// cout << endl << ans << endl << ans2 << endl;
		return ;
	}
	ask(ls(p),l,mid,L,R);
	ask(rs(p),mid+1,r,L,R);
}

int main(){
    ios::sync_with_stdio(0);
    cin >> n>>m;
    for (int i=1;i <= n;i++){
        cin >> a[i];
    }
	build(1,1,n);
    while (m--){
        int o;
        cin>> o;
        if (o == 1){
            int l,r;
            cin >> l >> r;
            if (r < l) swap(l,r);
			ans = -1e8;
			ans2 = 0;
			ask(1,1,n,l,r);
			cout << ans << endl;
        }
        else{
            int P,S;
            cin >> P >> S;
			a[P] = S;
			update(1,1,n,P,S);
        }
    }
    return 0;
}