# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 5e5 + ;

const int mod = 1e9+;

# define RG register

# define ST static

int n;

struct pa {

    int l, r, x;

    pa() {}

    pa(int l, int r, int x) : l(l), r(r), x(x) {}

    friend pa operator + (pa a, pa b) {

        pa c; c.x = a.x + b.x;

        c.l = a.l, c.r = b.r;

        return c;

    }

    friend bool operator < (pa a, pa b) {

        return a.x < b.x;

    }

    friend bool operator > (pa a, pa b) {

        return a.x > b.x;

    }

};

struct querys {

    pa lmx, rmx, mx, s;

    querys() {}

    querys(pa lmx, pa rmx, pa mx, pa s) : lmx(lmx), rmx(rmx), mx(mx), s(s) {}

};

namespace SMT {

    const int Ms = 1e6 + ;

    pa lmx[Ms], rmx[Ms], lmi[Ms], rmi[Ms], mx[Ms], mi[Ms], s[Ms];

    bool tag[Ms];        // -1

    # define ls (x<<)

    # define rs (x<<|)

    inline void up(int x) {

        if(!x) return ;

        lmx[x] = max(lmx[ls], s[ls] + lmx[rs]);

        lmi[x] = min(lmi[ls], s[ls] + lmi[rs]);

        rmx[x] = max(rmx[rs], rmx[ls] + s[rs]);

        rmi[x] = min(rmi[rs], rmi[ls] + s[rs]);

        mx[x] = max(mx[ls], mx[rs]);

        mx[x] = max(mx[x], rmx[ls] + lmx[rs]);

        mi[x] = min(mi[ls], mi[rs]);

        mi[x] = min(mi[x], rmi[ls] + lmi[rs]);

        s[x] = s[ls] + s[rs];

    }

    inline void pushtag(int x) {

        if(!x) return ;

        lmx[x].x = -lmx[x].x;

        rmx[x].x = -rmx[x].x;

        lmi[x].x = -lmi[x].x;

        rmi[x].x = -rmi[x].x;

        mx[x].x = -mx[x].x;

        mi[x].x = -mi[x].x;

        s[x].x = -s[x].x;

        swap(mx[x], mi[x]);

        swap(lmx[x], lmi[x]);

        swap(rmx[x], rmi[x]);

        tag[x] ^= ;

    }

    inline void down(int x) {

        if(!x) return ;

        if(!tag[x]) return ;

        pushtag(ls); pushtag(rs);

        tag[x] = ;

    }

    inline void change(int x, int l, int r, int ps, int d) {

        if(l == r) {

            s[x].l = s[x].r = lmx[x].l = lmx[x].r = rmx[x].l = rmx[x].r = lmi[x].l = lmi[x].r = rmi[x].l = rmi[x].r = l;

            mx[x].l = mx[x].r = mi[x].l = mi[x].r = l;

            s[x].x = mx[x].x = mi[x].x = lmx[x].x = lmi[x].x = rmx[x].x = rmi[x].x = d;

            tag[x] = ;

            return ;

        }

        down(x);

        int mid = l+r>>;

        if(ps <= mid) change(ls, l, mid, ps, d);

        else change(rs, mid+, r, ps, d);

        up(x);

    }

    inline void change2(int x, int l, int r, int L, int R) {

        if(L <= l && r <= R) {

            pushtag(x);

            return ;

        }

        down(x);

        int mid = l+r>>;

        if(L <= mid) change2(ls, l, mid, L, R);

        if(R > mid) change2(rs, mid+, r, L, R);

        up(x);

    }

    inline querys merge(querys a, querys b) {

        querys c;

        c.lmx = max(a.lmx, a.s+b.lmx);

        c.rmx = max(b.rmx, a.rmx+b.s);

        c.s = a.s + b.s;

        c.mx = max(a.mx, b.mx);

        c.mx = max(c.mx, a.rmx + b.lmx);

        return c;

    }

    inline querys query(int x, int l, int r, int L, int R) {

        if(L <= l && r <= R) return querys(lmx[x], rmx[x], mx[x], s[x]);

        down(x);

        int mid = l+r>>;

        if(R <= mid) return query(ls, l, mid, L, R);

        else if(L > mid) return query(rs, mid+, r, L, R);

        else return merge(query(ls, l, mid, L, mid), query(rs, mid+, r, mid+, R));

    }

    inline void debug(int x, int l, int r) {

        printf("x = %d, l = %d, r = %d : mx = %d, lmx = %d, rmx = %d\n", x, l, r, mx[x].x, mx[x].l, mx[x].r);

        if(l == r) return ;

        int mid = l+r>>;

        debug(ls, l, mid);

        debug(rs, mid+, r);

    }

}

int Left[], Right[], m;

int main() {

    cin >> n;

    for (int i=, t; i<=n; ++i) {

        scanf("%d", &t);

        SMT::change(, , n, i, t);

    }

    int Q, a, b, c;

    querys t;

    cin >> Q;

    while(Q--) {

        int opt; scanf("%d", &opt);

        if(!opt) {

            scanf("%d%d", &a, &b);

            SMT::change(, , n, a, b);

        } else {

            scanf("%d%d%d", &a, &b, &c);

            int s = ; m = ;

            while(c--) {

                t = SMT::query(, , n, a, b);

                if(t.mx.x < ) break;

                else s += t.mx.x;

//                cout << t.mx.l << " " << t.mx.r << " " << t.mx.x << endl;

                SMT::change2(, , n, t.mx.l, t.mx.r);

                ++m; Left[m] = t.mx.l, Right[m] = t.mx.r;

            }

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

            for (int i=m; i; --i) SMT::change2(, , n, Left[i], Right[i]);

        }

//        SMT::debug(1, 1, n);

    }

    return ;

}