#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#define ll long long
#define fp(a,b,c) for(ll a=b;a<=c;a++)
#define fd(a,b,c) for(ll a=b;a>=c;a--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fr first
#define sd second
#define mod 1000000007
#define inf 0x3f3f3f3f`

using namespace std;

inline int rd(){
	int x = 0, f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9')x = (x<<1) + (x<<3) + (ch^48),ch = getchar();
	return x * f;}
inline ll lrd(){
	ll x = 0, f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9')x = (x<<1) + (x<<3) + (ch^48),ch = getchar();
	return x * f;}

const int maxN=2*1e5+10;
struct node{
	ll ans,lmax,rmax,sum;
}tree[maxN*10];
int son[maxN*10][2],a[maxN],idx,n,m,root;
int lx[maxN*10],rx[maxN*10];

node pushup(node x,node y){
	node z;
	z.sum=x.sum+y.sum;
	z.lmax=max(x.lmax,x.sum+y.lmax);
	z.rmax=max(y.rmax,y.sum+x.rmax);
	z.ans=max(max(y.ans,x.ans),y.lmax+x.rmax);
	return z;
}

void insert(int &now,int x,int val,int l,int r){
	if(!now) now=++idx;
	lx[now]=l,rx[now]=r;
	if(l==r){
		tree[now]={val,val,val,val};
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid) insert(son[now][0],x,val,l,mid);
	else insert(son[now][1],x,val,mid+1,r);
	tree[now]=pushup(tree[son[now][0]],tree[son[now][1]]);
}

node query(int now,int l,int r){
	if(l<=lx[now]&&rx[now]<=r)
		return tree[now];
	int mid=(lx[now]+rx[now])>>1;
	if(r<=mid) return query(son[now][0],l,r);
	else if(l>mid) return query(son[now][1],l,r);
	else return pushup(query(son[now][0],l,r),query(son[now][1],l,r));
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0); 
	n=rd(),m=rd();
	fp(i,1,n) a[i]=rd(),insert(root,i,a[i],1,n);
	while(m--){
		int k,l,r;
		k=rd(),l=rd(),r=rd();
		if(k==1){
			if(l>r) swap(l,r);
			cout << query(root,l,r).ans << endl;
		}
		else insert(root,l,r,1,n);
	}
	
	
	
	
	return 0;
}