#include<iostream>
using namespace std;

const int N = 5 * 1e5 + 5;
//#define int long long 
#define lc u << 1
#define rc u << 1 | 1 
int n, m;
int a[N];
struct node{
	int l, r;
	int sum;
	int la, ra;
	int ans;
}t[N << 2];

void up(int u){
	t[u].sum = t[lc].sum + t[rc].sum;
	t[u].la = max(t[lc].la, t[lc].sum + t[rc].la);
	t[u].ra = max(t[rc].ra, t[rc].sum + t[lc].ra);
	t[u].ans = max(t[lc].ra + t[rc].la, max(t[lc].ans, t[rc].ans));
}

void build(int u, int l, int r){
	t[u] = {l, r, 0, 0, 0, 0};
	if(l == r){
		t[u].la = t[u].ra = t[u].ans = t[u].sum = a[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(lc, l, mid);
	build(rc, mid + 1, r);
	up(u);
}

node ask(int u, int l, int r){
	if(l <= t[u].l && t[u].r <= r){
		return t[u];
	}
	int mid = (t[u].l + t[u].r) >> 1;
	if(r <= mid) return ask(lc, l, r);
	if(l > mid) return ask(rc, l, r);
	node L, R, res;
	L = ask(lc, l, r);
	R = ask(rc, l, r);
	res.sum = L.sum + R.sum;
	res.la = max(L.la, L.sum + R.la);
	res.ra = max(R.ra, R.sum + L.ra);
	res.ans = max(max(L.ans, R.ans), L.ra + R.la);
	return res;
}

void add(int u, int x, int k){
	if(t[u].l == t[u].r){
		t[u].ans = t[u].la = t[u].ra = t[u].sum = k;
		return;
	}
	int mid = (t[u].l + t[u].r) >> 1;
	if(x <= mid) add(lc, x, k);
	else add(rc, x, k);
	up(u);
}

signed main(){
	
	cin >> n >> m;
	
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
	}
	
	build(1, 1, n);
	
	for(int i = 1;i <= m;i ++){
		int op; cin >> op;
		if(op == 1){
			int a, b; cin >> a >> b;
			if(a > b) swap(a, b);
			cout << ask(1, a, b).ans << '\n';
		}
		else{
			int x, k; cin >> x >> k;
			add(1, x, k);
		}
	}
	return 0;
}
