#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=+;

int n,m,a[maxn];

struct node{

    int lm,rm,sum,ans;

}tree[maxn*];

void pushup(int rt){

    tree[rt].lm=max(tree[rt<<].lm,tree[rt<<].sum+tree[rt<<|].lm);

    tree[rt].rm=max(tree[rt<<|].rm,tree[rt<<|].sum+tree[rt<<].rm);

    tree[rt].sum=tree[rt<<].sum+tree[rt<<|].sum;

    tree[rt].ans=max(max(tree[rt<<].ans,tree[rt<<|].ans),tree[rt<<].rm+tree[rt<<|].lm);

}

void build(int l,int r,int rt){

    if(l==r){

        tree[rt].lm=tree[rt].rm=tree[rt].sum=tree[rt].ans=a[l];

        return;

    }

    int mid=(l+r)>>;

    build(l,mid,rt<<);

    build(mid+,r,rt<<|);

    pushup(rt);

}

void update(int pos,int val,int l,int r,int rt){

    if(l==r){

        tree[rt].lm=tree[rt].rm=tree[rt].sum=tree[rt].ans=val;

        return;

    }

    int mid=(l+r)>>;

    if(pos<=mid) update(pos,val,l,mid,rt<<);

    else update(pos,val,mid+,r,rt<<|);

    pushup(rt);

}

node query(int L,int R,int l,int r,int rt){

    if(L<=l&&R>=r) return tree[rt];  //区间完全覆盖，直接返回该节点

    int mid=(l+r)>>;

    if(R<=mid) return query(L,R,l,mid,rt<<);  //只在左区间，直接查询左区间

    else if(L>mid) return query(L,R,mid+,r,rt<<|); //只在右区间，直接查询右区间

    else{ //左右区间都有，考虑如何合并

    //res1记录左覆盖区间，res2记录右覆盖区间

        node res,res1=query(L,mid,l,mid,rt<<),res2=query(mid+,R,mid+,r,rt<<|);

        res.lm=max(res1.lm,res1.sum+res2.lm);

        res.rm=max(res2.rm,res2.sum+res1.rm);

        res.ans=max(max(res1.ans,res2.ans),res1.rm+res2.lm);

        return res;

    }

}

int main(){

    scanf("%d%d",&n,&m);

    for(int i=;i<=n;i++)

        scanf("%d",&a[i]);

    build(,n,);

    while(m--){

        int op,x,y;

        scanf("%d%d%d",&op,&x,&y);

        if(op==){

            if(x>y) swap(x,y);

            printf("%d\n",query(x,y,,n,).ans);

        }else update(x,y,,n,);

    }

    return ;

}