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

const int N = 5e5 + 10;
struct Node {
	int sum, ls, rs, ms;
}seg[4 * N];

int a[N];

void pushup(int x) {
	seg[x].sum = seg[2 * x].sum + seg[2 * x + 1].sum;
	seg[x].ls = max(seg[2 * x].ls, seg[2 * x].sum + seg[2 * x + 1].ls);
	seg[x].rs = max(seg[2 * x + 1].rs, seg[2 * x + 1].sum + seg[2 * x].rs);
	seg[x].ms = max(max(seg[2 * x].ms, seg[2 * x + 1].ms), seg[2 * x].rs + seg[2 * x + 1].ls); 
}

void init(int x, int l, int r) {
	if (l == r) {
		seg[x].sum = seg[x].ls = seg[x].rs = seg[x].ms = a[l];
		return;
	}
	int mid = (l + r) / 2;
	init(2 * x, l, mid);
	init(2 * x + 1, mid + 1, r);
	pushup(x);
}

void update(int x, int l, int r, int p, int val) {
	if (p <= l && r <= p) {
		seg[x].sum = seg[x].ls = seg[x].rs = seg[x].ms = val;
		return;
	}
	int mid = (l + r) / 2;
	if (p <= mid)
		update(2 * x, l, mid, p, val);
	if (p > mid)
		update(2 * x + 1, mid + 1, r, p, val);
	pushup(x);
}

Node query(int x, int l, int r, int L, int R) {
	if (L <= l && r <= R) {
		return seg[x];
	}
	int mid = (l + r) / 2;
	Node f1, f2, ans;
    if (L <= mid && R > mid) {
        f1 = query(2 * x, l, mid, L, R);
        f2 = query(2 * x + 1, mid + 1, r, L, R);
        ans.sum = f1.sum + f2.sum;
        ans.ls = max(f1.ls, f1.sum + f2.ls);
        ans.rs = max(f2.rs, f2.sum + f1.rs);
        ans.ms = max(max(f1.ms, f2.ms), f1.rs + f2.ls);
    }
    if (R <= mid)
        ans = query(2 * x, l, mid, L, R);
    if (L > mid)
        ans = query(2 * x + 1, mid + 1, r, L, R);
	return ans;
}

int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	init(1, 1, n);
	while (m--) {
		int op;
		cin >> op;
		if (op == 1) {
			int x, y;
			cin >> x >> y;
			x = min(x, y), y = max(x, y);
			Node ans = query(1, 1, n, x, y);
			cout << ans.ms << "\n";
		}
		else {
			int p, s;
			cin >> p >> s;
			update(1, 1, n, p, s);
		}
	}
	return 0;
}