#include<iostream>
#define int long long
using namespace std;
struct node{
	int mal, mar, sum, ans;
}T[500005 << 2];
int a[500005];
int n, m;
inline int ls(int p) {
	return p << 1;
}
inline int rs(int p) {
	return p << 1 | 1;
}
void pushup(int p) {
	T[p].sum = T[ls(p)].sum + T[rs(p)].sum;
	T[p].ans = max( max(T[ls(p)].ans, T[rs(p)].ans), T[ls(p)].mar + T[rs(p)].mal);
	T[p].mal = max(T[ls(p)].mal, T[ls(p)].sum + T[rs(p)].mal);
	T[p].mar = max(T[rs(p)].mar, T[rs(p)].sum + T[ls(p)].mar);
}
void build(int l, int r, int p) {
	if(l == r) {
		T[p].sum = a[l];
		T[p].mal = T[p].mar = T[p].ans = T[p].sum;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, ls(p));
	build(mid + 1, r, rs(p));
	pushup(p);
}
node query(int sl, int sr, int l, int r, int p) {
	if(sl <= l and r <= sr) 
		return T[p];
	int mid = (l + r) >> 1;
	if(sl <= mid) 
	    return query(sl, sr, l, mid, ls(p));
	else {
		if(mid < sr) 
	    	return query(sl, sr, mid + 1, r, rs(p));
		else {
			node q, ll = query(sl, sr, l, mid, ls(p)), rr = query(sl, sr, mid + 1, r, rs(p));
			q.mal = max(ll.mal, ll.sum + rr.mal);
			q.mar = max(rr.mar, rr.sum + ll.mar);
			q.ans = max( max(ll.ans, rr.ans), ll.mar + rr.mal);
			return q;
		}
	}
}
void update(int sl, int l, int r, int p, int k) {
	if(l == r) {
		T[p].mal = T[p].mar = T[p].ans = T[p].sum = k;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= sl)
	    update(sl, l, mid, ls(p), k);
	else 
	    update(sl, mid + 1, r, rs(p), k);
	pushup(p);
}
signed main() {
	std::ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i = 1; i <= n; i++)
	    cin>>a[i];
	build(1, n, 1);
	int op, x, y;
	while(m--) {
		cin>>op>>x>>y;
		if(op == 1) {
			if(x > y) 
			    swap(x, y);
			cout<<query(x, y, 1, n, 1).ans<<'\n';
		}
		else 
		    update(x, 1, n, 1, y);
	}
	return 0;
}