#include <cstdio>

using namespace std;
int N;
int i, j, k, l;
int  v[200001];
int  B[800001];
int BS[800001];
int BD[800001];
int  S[800001];
int CC = 0, QQ = 0; //rezerva
int p1, p2;
void repara(int nod, int a, int b) {
	if (b < a) {B[nod] = -999999; BS[nod] = -999999; BD[nod] = -999999; S[nod] = -999999; return;}
	if (QQ > b || QQ < a)  return;
	if (a==b) {B[nod] = CC; BS[nod] = CC; BD[nod] = CC; S[nod] = CC; return;};
	repara(2*nod, a, (a+b)/2);
	repara(2*nod+1, (a+b)/2+1, b);
	S[nod] = 0;
	if (a <= (a+b)/2) S[nod] = S[2*nod];
	if ((a+b)/2 +1 <=b) S[nod]+= S[2*nod+1];
	//S[nod] = S[2*nod] + S[2*nod+1];
	B[nod] = B[2*nod]; if ((a+b)/2+1 <= b && B[2*nod+1] > B[nod]) B[nod] = B[2*nod+1];
	if ((a+b)/2+1 <= b && BS[2*nod+1] + BD[2*nod] > B[nod]) B[nod] = BS[2*nod+1] + BD[2*nod];
	BS[nod] = BS[2*nod]; if ((a+b)/2+1 <= b && S[2*nod] + BS[2*nod+1] > BS[nod]) BS[nod] = S[2*nod] + BS[2*nod+1];
	BD[nod] = BD[2*nod+1]; if ((a+b)/2+1 <= b && S[2*nod+1] + BD[2*nod] > BD[nod] ) BD[nod] = S[2*nod+1]+BD[2*nod];
	if (BS[nod] > B[nod]) B[nod] = BS[nod];
	if (BD[nod] > B[nod]) B[nod] = BD[nod];
	if (S[nod] > B[nod]) B[nod] = S[nod];
	}
int solve(int nod, int a, int b, int T, int p1, int p2) {
	if (p2 < a) return -999999;
	if (p1 > b) return -999999;
	if (p1 <= a && p2 >= b) {
		if (T == 0) {return S[nod];}
		if (T == 1) {
		//	if (BS[nod] < 0) return 0;
					return BS[nod];}
		if (T == 2) {
		//	if(BD[nod] < 0) return 0; 
			return BD[nod];}
		if (T == 3) {//if (B[nod] < 0) return 0; 
					return B[nod];}
		};
	int mid = a + b; mid/=2;
	int ret = 0;
	if (T == 0) return solve(2*nod, a, mid, 0, p1, p2) + solve(2*nod+1, mid+1, b, 0, p1, p2);
	if (T == 1) {
		//[p1....p2]
		//ret = 0;
		if (p1 <= mid &&p2 > mid) {
				int X2 = solve(2*nod, a, mid, 1, p1, mid);
				int X = solve(2*nod, a, mid, 0, p1, mid) + solve(2*nod+1, mid+1, b, 1,mid+1,p2);
			//	int X = solve(2*nod, a, mid, 2) + solve(2*nod+1,mid+1, b,1);
				if (X > X2) return X;
				return X2;}
		else if (p2 <= mid) return solve(2*nod, a, mid,  1, p1, p2);
		else return solve(2*nod+1, mid+1, b, 1, p1, p2);
		//[p1, mid] + t=1 -> [mid+1, p2];
		//[
		}
	if (T == 2) {
		if (p1 <= mid && p2 > mid) {
			int X= solve(2*nod+1, mid+1, b, 2, mid+1, p2);
			int X2 =solve(2*nod+1, mid+1, b,  0, mid+1, p2) + solve(nod*2, a, mid, 2 ,p1, mid); 
			if (X2 > X) return X2;
			return  X; }
		else if (p2 <= mid) return solve(2*nod, a, mid,  2, p1, p2);
		else return solve(2*nod+1, mid+1, b, 2, p1, p2);
		}
	if (T == 3) {
		if (p2 <= mid) return solve(2*nod, a, mid,  3, p1, p2);
		else if (p1 > mid) return solve(2*nod+1, mid+1, b,  3, p1, p2);
		else {
			int X1 = solve(2*nod, a, mid,  2, p1, mid), X2 =  solve(2*nod+1, mid+1, b, 1, mid+1, p2);
			int R;		
			R = X1+ X2;
			X1 = solve(2*nod, a, mid, 3, p1, mid);
			X2 = solve(2*nod+1, mid+1, b, 3, mid+1, p2);
			if (X1 > R) R = X1;
			if (X2 > R) R = X2;
			return  R;
			}
		}
	}
int main() {
	freopen("sequencequery.in", "r", stdin);
	freopen("sequencequery.out", "w", stdout);
	int M;
	scanf("%d %d", &N, &M);
	for (i=1; i<=N; i++) { scanf("%d", &v[i]); CC = v[i]; QQ = i; repara(1, 1, N);}
	
	//scanf("%d", &M);
	while (M--) {
		int a1=8, a2, a3;
		scanf("%d %d", &a2, &a3);
		if (a1 == 0) {CC = a3; QQ = a2+1; repara(1, 1, N);}
		else {
			QQ = -200000;	
			//a2++; a3++;
			p1 = a2; p2 = a3;
			QQ = solve(1, 1, N,  3, a2, a3);
			//if (QQ < 0) QQ = 0; 
			printf("%d\n", QQ);
			}
		}
	return 0;
}