#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N = ;

template<typename T>

inline void read(T&x)

{

    T f = ,c = ;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}

    x = f*c;

}

int n,m;

int chg[][];

struct n_8

{

    int w,wl,wr,wu,pl,pr,pll,prr;

    n_8(){}

    n_8(int w,int wl,int wr,int wu,int pl,int pr,int pll,int prr):w(w),wl(wl),wr(wr),wu(wu),pl(pl),pr(pr),pll(pll),prr(prr){}

};

void chkmax(int&a,int&b,int c,int d,int e,int f)

{

    if(c>e)a=c,b=d;

    else a=e,b=f;

}

void chkmax(int&a,int&b,int&c,int d,int e,int f,int g,int h,int i)

{

    if(d>g)a=d,b=e,c=f;

    else a=g,b=h,c=i;

}

void chkmin(int&a,int&b,int c,int d,int e,int f)

{

    if(c<e)a=c,b=d;

    else a=e,b=f;

}

void chkmin(int&a,int&b,int&c,int d,int e,int f,int g,int h,int i)

{

    if(d<g)a=d,b=e,c=f;

    else a=g,b=h,c=i;

}

void Swap(int&a,int&b)

{

    swap(a,b);

    a=-a,b=-b;

}

n_8 operator + (n_8 a,n_8 b)

{

    n_8 c;

    c.w = a.w+b.w;

    chkmax(c.wl,c.pll,a.wl,a.pll,a.w+b.wl,b.pll);

    chkmax(c.wr,c.prr,b.wr,b.prr,b.w+a.wr,a.prr);

    chkmax(c.wu,c.pl,c.pr,a.wu,a.pl,a.pr,b.wu,b.pl,b.pr);

    chkmax(c.wu,c.pl,c.pr,c.wu,c.pl,c.pr,a.wr+b.wl,a.prr,b.pll);

    return c;

}

struct segtree

{

    int w[N<<],wl[N<<],wr[N<<],wu[N<<],pl[N<<],pr[N<<],pll[N<<],prr[N<<];

    int _wl[N<<],_wr[N<<],_wu[N<<],_pl[N<<],_pr[N<<],_pll[N<<],_prr[N<<];

    bool res[N<<];

    void update(int u)

    {

        w[u] = w[u<<]+w[u<<|];

        chkmax(wl[u],pll[u],wl[u<<],pll[u<<],w[u<<]+wl[u<<|],pll[u<<|]);

        chkmax(wr[u],prr[u],wr[u<<|],prr[u<<|],w[u<<|]+wr[u<<],prr[u<<]);

        chkmin(_wl[u],_pll[u],_wl[u<<],_pll[u<<],w[u<<]+_wl[u<<|],_pll[u<<|]);

        chkmin(_wr[u],_prr[u],_wr[u<<|],_prr[u<<|],w[u<<|]+_wr[u<<],_prr[u<<]);

        chkmax(wu[u],pl[u],pr[u],wu[u<<],pl[u<<],pr[u<<],wu[u<<|],pl[u<<|],pr[u<<|]);

        chkmax(wu[u],pl[u],pr[u],wu[u],pl[u],pr[u],wr[u<<]+wl[u<<|],prr[u<<],pll[u<<|]);

        chkmin(_wu[u],_pl[u],_pr[u],_wu[u<<],_pl[u<<],_pr[u<<],_wu[u<<|],_pl[u<<|],_pr[u<<|]);

        chkmin(_wu[u],_pl[u],_pr[u],_wu[u],_pl[u],_pr[u],_wr[u<<]+_wl[u<<|],_prr[u<<],_pll[u<<|]);

    }

    void reser(int u)

    {

        res[u]^=;

        w[u] = -w[u];

        Swap(wl[u],_wl[u]);Swap(wr[u],_wr[u]);Swap(wu[u],_wu[u]);

        swap(pl[u],_pl[u]);swap(pr[u],_pr[u]);

        swap(pll[u],_pll[u]);swap(prr[u],_prr[u]);

    }

    void pushdown(int u)

    {

        if(res[u])

        {

            reser(u<<);

            reser(u<<|);

            res[u] = ;

        }

    }

    void build(int l,int r,int u)

    {

        if(l==r)

        {

            int x;read(x);

            w[u] = wu[u] = _wu[u] = wl[u] = _wl[u] = wr[u] = _wr[u] = x;

            pl[u]=pr[u]=pll[u]=prr[u]=_pl[u]=_pr[u]=_pll[u]=_prr[u]=l;

            return ;

        }

        int mid = (l+r)>>;

        build(l,mid,u<<);

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

        update(u);

    }

    void insert(int l,int r,int u,int qx,int d)

    {

        if(l==r)

        {

            w[u] = wu[u] = _wu[u] = wl[u] = _wl[u] = wr[u] = _wr[u] = d;

            return ;

        }

        pushdown(u);

        int mid = (l+r)>>;

        if(qx<=mid)insert(l,mid,u<<,qx,d);

        else insert(mid+,r,u<<|,qx,d);

        update(u);

    }

    void erase(int l,int r,int u,int ql,int qr)

    {

        if(l==ql&&r==qr)

        {

            reser(u);

            return ;

        }

        pushdown(u);

        int mid = (l+r)>>;

        if(qr<=mid)erase(l,mid,u<<,ql,qr);

        else if(ql>mid)erase(mid+,r,u<<|,ql,qr);

        else erase(l,mid,u<<,ql,mid),erase(mid+,r,u<<|,mid+,qr);

        update(u);

    }

    n_8 query(int l,int r,int u,int ql,int qr)

    {

        if(l==ql&&r==qr)return n_8(w[u],wl[u],wr[u],wu[u],pl[u],pr[u],pll[u],prr[u]);

        pushdown(u);

        int mid = (l+r)>>;

        if(qr<=mid)return query(l,mid,u<<,ql,qr);

        else if(ql>mid)return query(mid+,r,u<<|,ql,qr);

        else return query(l,mid,u<<,ql,mid)+query(mid+,r,u<<|,mid+,qr);

    }

}tr;

int main()

{

    read(n);

    tr.build(,n,);

    read(m);

    int op,x,y,w;

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

    {

        read(op),read(x),read(y);

        if(!op)tr.insert(,n,,x,y);

        else

        {

            read(w);

            n_8 tmp = tr.query(,n,,x,y);

            int ans = ;

            for(int j=;j<=w;j++)

            {

                if(tmp.wu>)

                {

                    ans+=tmp.wu;

                    chg[j][]=tmp.pl,chg[j][]=tmp.pr;

                    tr.erase(,n,,tmp.pl,tmp.pr);

                    tmp = tr.query(,n,,x,y);

                }else

                {

                    w = j-;

                    break;

                }

            }

            printf("%d\n",ans);

            for(int j=;j<=w;j++)

                tr.erase(,n,,chg[j][],chg[j][]);

        }

    }

    return ;

}