/*
线段树优化dp
考虑最大子段和的生成情况，可得到如下方程：
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
tree[p].lmax=max(tree[p<<1].lmax,tree[p<<1].sum+tree[p<<1|1].lmax);
tree[p].rmax=max(tree[p<<1|1].rmax,tree[p<<1|1].sum+tree[p<<1].rmax);
tree[p].dat=max(tree[p<<1].dat,max(tree[p<<1|1].dat,tree[p<<1].rmax+tree[p<<1|1].lmax));
sum是区间和
lmax是紧靠区间左端点的最大子段和
rmax是紧靠区间右端点的最大子段和
dat是整个区间的最大子段和
*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=500000+5;
const int INF=0x3f3f3f3f;
int n,m,a[maxn];
struct node {
    int l,r,sum,lmax,rmax,dat;
    node(int tmp=0) {
        sum=lmax=rmax=dat=tmp;
    }
} tree[maxn<<2];
void build(int p,int l,int r) {
    tree[p].l=l,tree[p].r=r;
    if(l==r) {
        tree[p].sum=tree[p].dat=tree[p].lmax=tree[p].rmax=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
    tree[p].lmax=max(tree[p<<1].lmax,tree[p<<1].sum+tree[p<<1|1].lmax);
    tree[p].rmax=max(tree[p<<1|1].rmax,tree[p<<1|1].sum+tree[p<<1].rmax);
//  tree[p].dat=max(tree[p<<1].dat,tree[p<<1|1].dat);
    tree[p].dat=max(tree[p<<1].dat,max(tree[p<<1|1].dat,tree[p<<1].rmax+tree[p<<1|1].lmax));
}
void change(int p,int x,int v) {
    if(tree[p].l==tree[p].r) {
        tree[p].sum=tree[p].dat=tree[p].lmax=tree[p].rmax=v;
        return;
    }
    int mid=(tree[p].l+tree[p].r)>>1;
    if(x<=mid) change(p<<1,x,v);
    else change(p<<1|1,x,v);
    tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
    tree[p].lmax=max(tree[p<<1].lmax,tree[p<<1].sum+tree[p<<1|1].lmax);
    tree[p].rmax=max(tree[p<<1|1].rmax,tree[p<<1|1].sum+tree[p<<1].rmax);
    tree[p].dat=max(tree[p<<1].dat,max(tree[p<<1|1].dat,tree[p<<1].rmax+tree[p<<1|1].lmax));
}
node ask(int p,int l,int r) {
    if(l<=tree[p].l&&r>=tree[p].r) {
        return tree[p];
    }
    int mid=(tree[p].l+tree[p].r)>>1;
//  int val=-INF;
    node a,b,c;
    if(r<=mid) return ask(p<<1,l,r);
    if(l>=mid+1) return ask(p<<1|1,l,r);
    else{
        a=ask(p<<1,l,r);
    b=ask(p<<1|1,l,r);
    c.sum=a.sum+b.sum;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.dat=max(a.dat,max(b.dat,a.rmax+b.lmax));
    return c;
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        cin>>a[i];
    }
    build(1,1,n);
    int x,y,z;
    while(m--)
    {
        cin>>x>>y>>z;
//      if(y>z) swap(y,z); //不能在这里swap 会影响命令2 
        if(x==1)cout<<ask(1,min(y,z),max(y,z)).dat<<endl;
        else change(1,y,z);
    }
    return 0;
}
#endif