#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cout<<#x<<": "<<x<<endl
#define ls p << 1
#define rs (p << 1) + 1
typedef long long ll;
using namespace std;
const int N = 5e5 + 50;
const int INF = 1e9;

int n, m, a[N];

struct Segment_Tree {
	int l, r, lsum, rsum, sum, ans;
} tr[N << 2];

void pushup(int p) {
	tr[p].ans = max(max(tr[ls].ans, tr[rs].ans), tr[ls].rsum + tr[rs].lsum);
	tr[p].lsum = max(tr[ls].lsum, tr[ls].sum + tr[rs].lsum);
	tr[p].rsum = max(tr[rs].rsum, tr[ls].rsum + tr[rs].sum);
	tr[p].sum = tr[ls].sum + tr[rs].sum;
}

void build(int p, int l, int r) {
	tr[p].l = l, tr[p].r = r;
	tr[p].ans = tr[p].lsum = tr[p].rsum = tr[p].sum = -INF;
	
	if(l == r) {
		tr[p].ans = tr[p].lsum = tr[p].rsum = tr[p].sum = a[l];
		return ;
	}

	int mid = (l + r) >> 1;
	build(ls, l, mid);
	build(rs, mid + 1, r);

	pushup(p);
}

void updata(int p, int pos, int num) {
	if(tr[p].l == tr[p].r) {
		tr[p].ans = tr[p].lsum = tr[p].rsum = tr[p].sum = num;
		return ;
	}

	int mid = (tr[p].l + tr[p].r) >> 1;
	if(pos <= mid) updata(ls, pos, num);
	else updata(rs, pos, num);

	pushup(p);
}

int query(int p, int l, int r) {
	if(tr[p].l >= l && tr[p].r <= r) return tr[p].ans;

	int mid = (tr[p].l + tr[p].r) >> 1, ans = -INF;
	if(l <= mid && r >= mid + 1)
		ans = max(max(query(ls, l, r), query(rs, l, r)), tr[ls].rsum + tr[rs].lsum);
	else if(r <= mid) ans = query(ls, l, r);
	else if(l > mid) ans = query(rs, l, r);

	return ans;
}

int main() {
	FAST;
	cin>>n>>m;
	for(int i=1; i<=n; ++i) cin>>a[i];

	build(1, 1, n);

	int q, l, r;
	for(int i=1; i<=m; ++i) {
		cin>>q>>l>>r;
		if(q == 1) {
			if(l > r) swap(l, r);
			cout<<query(1, l, r)<<endl;
		} else updata(1, l, r);
	}

	return 0;
}