#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n,m;
int a[N];
struct node{
	int l,r;
	int sum;
	int maxx,qmaxx,hmaxx;
}tr[4 * N];
void push_up(int u){
   tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
   tr[u].maxx = max(max(tr[u << 1].maxx,tr[u << 1 | 1].maxx),tr[u << 1].hmaxx + tr[u << 1 | 1].qmaxx);
   tr[u].qmaxx = max(tr[u << 1].qmaxx,tr[u << 1].sum + tr[u << 1 | 1].qmaxx);
   tr[u].hmaxx = max(tr[u << 1 | 1].hmaxx,tr[u << 1].hmaxx + tr[u << 1 | 1].sum);
}
void pushup(node &u,node &l,node &r){
	u.sum = l.sum + r.sum;
	u.qmaxx = max(l.qmaxx,l.sum + r.qmaxx);
	u.hmaxx = max(r.hmaxx,r.sum + l.hmaxx);
	u.maxx = max(max(l.maxx,r.maxx),l.hmaxx + r.qmaxx);
}
void build(int u,int l,int r){
	tr[u].l = l,tr[u].r = r;
	if(l == r){
		tr[u].sum = tr[u].qmaxx = tr[u].hmaxx = tr[u].maxx = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(u << 1,l,mid);
	build(u << 1 | 1,mid + 1,r);
	push_up(u); 
}
void modify(int u,int a,int b){
	if(tr[u].l == a && tr[u].r == a){
		tr[u].sum = tr[u].maxx = tr[u].qmaxx = tr[u].hmaxx = b;
		return;
	}
	int mid = tr[u].l + tr[u].r >> 1;
	if(a <= mid) modify(u << 1,a,b);
	else modify(u << 1 | 1,a,b);
	push_up(u);
}
node query(int u,int l,int r){
	cout << 1 << " ";
	if(tr[u].l >= l && r >= tr[u].r){
		return tr[u];
	}
	int mid = tr[u].l + tr[u].r >> 1;
	 if(l > mid) return query(u << 1,l,r);
	 else if(r <= mid)  return query(u << 1 | 1,l,r);
	 else {
	 	node left = query(u << 1,l,r);
	 	node right = query(u << 1 | 1,l,r);
	 	node ans;
	 	pushup(ans,left,right);
	 	return ans;
	 }
}
int main(){
	cin >> n >> m;
	for(int i = 1; i <= n ; i++) cin >> a[i];
	build(1,1,n);
	while(m--){
		int k,a,b;
		cin >> k >> a >> b;
		 if(k == 1){
		  if(a > b) swap(a,b);
		  cout << query(1,a,b).maxx << endl;
		}
		else{
			modify(1,a,b);
		}
	}
	return 0;
}