using namespace std;
#include <cstdio>
#include <algorithm>


#define FIN "datorii.in"
#define FOUT "datorii.out"

#define MAX_N (1<<14)
#define max(a, b) ((a) > (b) ? (a) : (b))

int N, M;
int v[MAX_N];
long long A[MAX_N<<1], B[MAX_N<<1], C[MAX_N<<1], Sum[MAX_N<<1];

#define lf (n<<1)
#define rt (lf+1)
#define md ((l+r)>>1)

void build(int n, int l, int r)
{
	if (l == r) {
		A[n] = B[n] = C[n] = max(v[l], 0);
		Sum[n] = v[l];
	} else {
		build(lf, l, md);
		build(rt, md+1, r);

		A[n] = max(A[lf], Sum[lf]+A[rt]);
		B[n] = max(B[lf]+Sum[rt], B[rt]);
		C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);
		
		Sum[n] = Sum[lf]+Sum[rt];
	}
}

int p, x;

void update(int n, int l, int r) 
{
	if (l == r) {
		A[n] = B[n] = C[n] = max(x, 0);
		Sum[n] = x;
	} else {
		if (p <= md) update(lf,    l, md);
		else         update(rt, md+1,  r);

		A[n] = max(A[lf], Sum[lf]+A[rt]);
		B[n] = max(B[lf]+Sum[rt], B[rt]);
		C[n] = max(max(C[lf], C[rt]), B[lf]+A[rt]);
		
		Sum[n] = Sum[lf]+Sum[rt];		
	}
}

int a, b;
long long ans, S;

void query(int n, int l, int r) 
{
	if (a <= l && r <= b) {
		if (S < 0) S = 0;
		ans = max(ans, max(S+A[n], C[n]));
		S = max(S+Sum[n], B[n]);
	} else {
		if (a <= md) query(lf,    l, md);
		if (b >  md) query(rt, md+1,  r);
	}
}

int main()
{
	int i, t, v1, v2;
	
	freopen(FIN, "r", stdin);
	freopen(FOUT, "w", stdout);

	scanf("%d %d", &N,&M);
	for (i = 1; i <= N; ++i)
		scanf("%d", v+i);
	build(1, 1, N);
	while (M--) {
		scanf("%d %d %d", &t, &v1, &v2);
		if (t == 0) 
          { 
			p = v1; x = v[v1]-v2;
			update(1, 1, N);
          } 
        else 
          { 
			S = ans = 0;
			a = v1; b = v2;
			query(1, 1, N);

			printf("%lld\n", ans);
  	      }
	}
	return 0;
}