RT

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const ll MAXN = 1e5 + 10;
int n, m;
struct node {
	ll l, r;
	ll data;
	ll lmax, rmax, tmax;
} tree[MAXN << 2];
ll a[MAXN];
void update(ll p) {
	tree[p].data = tree[p << 1].data + tree[p << 1 | 1].data;
	tree[p].lmax = max(tree[p << 1].lmax, tree[p << 1].data + tree[p << 1 | 1].lmax);
	tree[p].rmax = max(tree[p << 1 | 1].rmax, tree[p << 1 | 1].data + tree[p << 1].rmax);
	tree[p].tmax = max(max(tree[p << 1].tmax, tree[p << 1 | 1].tmax), tree[p << 1].rmax + tree[p << 1 | 1].lmax);
}
void build(ll p, ll l, ll r) {
	tree[p].l = l;
	tree[p].r = r;
	if (l == r) {
		tree[p].data = tree[p].lmax = tree[p].rmax = tree[p].tmax = a[l];
		return;
	}
	ll mid = (l + r) >> 1;
	build(p << 1, l, mid);
	build(p << 1 | 1, mid + 1, r);
	update(p);
}
node query(ll p, ll l, ll r) {
	if (tree[p].l >= l && tree[p].r <= r) {
		return tree[p];
	}
	node lnode, rnode, tnode;
	tnode.data = 0;
	if (tree[p << 1].r >= l && tree[p << 1 | 1].l <= r) {
		lnode = query(p << 1, l, r);
		rnode = query(p << 1 | 1, l, r);
		tnode.data = lnode.data + rnode.data;
		tnode.lmax = max(lnode.lmax, lnode.data + rnode.lmax);
		tnode.rmax = max(rnode.rmax, rnode.data + lnode.rmax);
		tnode.tmax = max(max(lnode.tmax, rnode.tmax), lnode.rmax + rnode.lmax);
	}
	else if (tree[p << 1].r >= l) tnode = query(p << 1, l, r);
	else if (tree[p << 1 | 1].l <= r) tnode = query(p << 1 | 1, l, r);
	return tnode;
}
void modify(ll p, ll l, ll r, ll val) {
	if (tree[p].l == tree[p].r) {
		tree[p].data = tree[p].lmax = tree[p].rmax = tree[p].tmax = val;
		return;
	}
	if (tree[p << 1].r >= l) modify(p << 1, l, r, val);
	if (tree[p << 1 | 1].l <= r) modify(p << 1 | 1, l, r, val);
	update(p);
}
int main() {
	cin >> n >> m;
	for (ll i = 1; i <= n; i ++) cin >> a[i];
	build(1, 1, n);
	while (m --) {
		int opt, x, y;
		cin >> opt >> x >> y;
		if (opt == 1) {
			if (x > y) swap(x, y);
			cout << query(1, x, y).tmax << endl;
		}
		else modify(1, x, x, y);
	}
	return 0;
}