#include <iostream>
#include <cstdio>
#define ls(x) (x<<1)
#define rs(x) (x<<1)|1
#define int long long

using namespace std;

const int N = 5e5 + 1;

struct tree {
	int l, r;
	int sum;
	int ans;
	int maxleft, maxright;
} t[N << 2];

int n, m;
int a[N];

void pushup(int x) {
	t[x].sum = t[ls(x)].sum + t[rs(x)].sum;
	t[x].maxleft = max(t[ls(x)].maxleft, t[ls(x)].sum + t[rs(x)].maxleft);
	t[x].maxright = max(t[rs(x)].maxright, t[rs(x)].sum + t[ls(x)].maxright);
	t[x].ans = max(t[ls(x)].ans, max(t[rs(x)].ans, t[ls(x)].maxright + t[rs(x)].maxleft));
	return;
}

void build(int l, int r, int x) {
	t[x].l = l, t[x].r = r;
	if (l == r) {
		scanf("%lld", &t[x].sum);
		t[x].maxleft = t[x].maxright = t[x].ans = t[x].sum;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, ls(x)), build(mid + 1, r, rs(x));
	pushup(x);
	return;
}

void update(int l, int k, int x) {
	if (t[x].l == t[x].r) {
		t[x].sum = t[x].maxleft = t[x].maxright = t[x].ans = k;
		return;
	}
	int mid = (t[x].l + t[x].r) >> 1;
	if (l <= mid)
		update(l, k, ls(x));
	else
		update(l, k, rs(x));
	pushup(x);
	return;
}

tree ask(int l, int r, int x) {
	if (l <= t[x].l && t[x].r <= r)
		return t[x];
	int mid = (t[x].l + t[x].r) >> 1;
	if (r <= mid)
		return ask(l, r, ls(x));
	else if (l > mid)
		return ask(l, r, rs(x));
	else {
		tree tmp, a = ask(l, r, ls(x)), b = ask(l, r, rs(x));
		tmp.sum = a.sum + b.sum;
		tmp.maxleft = max(a.maxleft, a.sum + b.maxleft);
		tmp.maxright = max(b.maxright, a.sum + b.maxright);
		tmp.ans = max(a.ans, max(b.ans, a.maxright + b.maxleft));
		return tmp;
	}
}

signed main() {
	scanf("%lld%lld", &n, &m);
	build(1, n, 1);
	while (m -- ) {
		int op, x, y;
		scanf("%lld%lld%lld", &op, &x, &y);
		if (op == 1) {
			if (x > y)
				swap(x, y);
			printf("%lld\n", ask(x, y, 1).ans);
		} else if (op == 2)
			update(x, y, 1);
	}
	return 0;
}