#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 7;
#define ls x * 2
#define rs x * 2 + 1
int n, q;
struct node {
	int l, r;
	int lmax, rmax, max, sum;
}t[N << 2];
int a[N];
void push_up(int x) {
	t[x].sum = t[ls].sum + t[rs].sum;
	t[x].lmax = max(t[ls].lmax, t[ls].sum + t[rs].lmax);
	t[x].rmax = max(t[rs].rmax, t[rs].max + t[ls].rmax);
	t[x].max = max(t[ls].max, max(t[rs].max, t[ls].rmax + t[rs].lmax));
}
void build(int x, int l, int r) {
	t[x].l = l;
	t[x].r = r;
	if (l == r) {
		t[x].lmax = t[x].rmax = t[x].max = t[x].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);
	push_up(x);
}
void update(int x, int p, int d) {
	if (t[x].l == t[x].r) {
		t[x].sum = t[x].lmax = t[x].rmax = t[x].max = d;
		return;
	}
	int mid = (t[x].l + t[x].r) >> 1;
	if (p <= mid) {
		update(ls, p, d);
	}
	else {
		update(rs, p, d);
	}
	push_up(x);
}
node query(int x, int l, int r) {
	if (t[x].l >= l && t[x].r <= r) {
		return t[x];
	}
	int mid = (t[x].l + t[x].r) >> 1;
	if (r <= mid) {
		return query(ls, l, r);
	}
	else {
		if (l > mid) {
			return query(rs, l, r);
		}
		else {
			node ti, li = query(ls, l, r), ri = query(rs, l, r);
			ti.lmax = max(li.lmax, li.sum + ri.lmax);
			ti.rmax = max(ri.rmax, ri.sum + li.rmax);
			ti.max = max(li.max, max(ri.max, li.rmax + ri.lmax));
			return ti;
		}
	}
}
int main() {
	scanf("%d%d", &n, &q);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	build(1, 1, n);
	while (q--) {
		int opt;
		scanf("%d", &opt);
		if (opt == 1) {
			int l, r;
			scanf("%d%d", &l, &r);
			if (l > r) {
				swap(l, r);
			}
			printf("%d\n", query(1, l, r).max);
		}
		else {
			int p, d;
			scanf("%d%d", &p, &d);
			update(1, p, d);
		}
	}
	return 0;
}