#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define mp make_pair
using namespace std;
auto IN = freopen("hod.in", "r", stdin);
auto OUT = freopen("hod.out", "w", stdout);
auto IOS = ios::sync_with_stdio(false);
auto CIN = cin.tie(nullptr);
int mread(){
    int x = 0, f = 1;
    char c = cin.get();
    while(c < '0' || c > '9'){
        if(c == '-'){
            f = -1;
        }
        c = cin.get();
    }
    while(c >= '0' && c <= '9'){
        x = x * 10 + c - '0';
        c = cin.get();
    }
    return x * f;
}
const int inf = 0x3f3f3f3f3f3f3f3f, N = 5e4 + 5;
int n = mread(), a[N], q, b;
struct line{
    int k, b;
    // kx + b
    int get(int x){
        return k * x + b;
    }
};
struct tree{
    vector<line> s;
    vector<int> ls, rs;
    int idx = 1;
    void build(){
        s.push_back({0, -inf});
        ls.push_back(0);
        rs.push_back(0);
        return;
    }
    tree(){
        build();
        build();
        build();
        build();
        build();
    }
    void rebuild(){
        idx = 1;
        s = vector<line>(5, {0, -inf});
        ls = rs = vector<int>(5, 0);
    }
    void update(line k, int x = 1, int nl = -1.5e9, int nr = 1.5e9){
        int mid = nl + nr >> 1;
        if(k.get(mid) > s[x].get(mid)){
            swap(s[x], k);
        }
        // 认为 k 比较小，需要下传
        if(k.get(nl) > s[x].get(nl)){
            if(ls[x] == 0){
                ls[x] = ++idx;
                build();
            }
            update(k, ls[x], nl, mid);
        }
        if(k.get(nr) > s[x].get(nr)){
            if(rs[x] == 0){
                rs[x] = ++idx;
                build();
            }
            update(k, rs[x], mid + 1, nr);
        }
        return;
    }
    int query(int p, int x = 1, int nl = -1.5e9, int nr = 1.5e9){
        if(x == 0){
            return -inf;
        }
        if(nl == nr){
            return s[x].get(p);
        }
        int mid = nl + nr >> 1;
        if(p <= mid){
            return max(s[x].get(p), query(p, ls[x], nl, mid));
        }
        else{
            return max(s[x].get(p), query(p, rs[x], mid + 1, nr));
        }
    }
};
struct node{
    int l, r, s, d;
}s[N];
tree tr[305];
int belong[N];
int query(int l, int r){
    int x = belong[l], y = belong[r];
    if(x == y){
        int ans = -inf;
        for(int i = l; i <= r; i ++){
            ans = max(ans, a[i] + s[x].s + (i - s[x].l) * s[x].d);
        }
        return ans;
    }
    int ans = -inf;
    for(int i = x + 1; i < y; i ++){
        ans = max(ans, s[i].s + tr[i].query(s[i].d));
    }
    for(int i = l; i <= s[x].r; i ++){
        ans = max(ans, a[i] + s[x].s + (i - s[x].l) * s[x].d);
    }
    for(int i = s[y].l; i <= r; i ++){
        ans = max(ans, a[i] + s[y].s + (i - s[y].l) * s[y].d);
    }
    return ans;
}
void build(int x){
    for(int i = s[x].l; i <= s[x].r; i ++){
        a[i] = a[i] + s[x].s + (i - s[x].l) * s[x].d;
    }
    tr[x].rebuild();
    for(int i = s[x].l; i <= s[x].r; i ++){
        tr[x].update({i - s[x].l, a[i]});
    }
    s[x].s = s[x].d = 0;
    return;
}
void add(int l, int r, int k){
    int x = belong[l], y = belong[r];
    if(x == y){
        for(int i = l; i <= r; i ++){
            a[i] += (i - l + 1) * k;
        }
        build(x);
        return;
    }
    for(int i = x + 1; i < y; i ++){
        s[i].s += (s[i].l - l + 1) * k;
        s[i].d += k;
    }
    for(int i = l; i <= s[x].r; i ++){
        a[i] += (i - l + 1) * k;
    }
    build(x);
    for(int i = s[y].l; i <= r; i ++){
        a[i] += (i - l + 1) * k;
    }
    build(y);
    return;
}
void add2(int l, int r, int k){
    int x = belong[l], y = belong[r];
    if(x == y){
        for(int i = l; i <= r; i ++){
            a[i] += k;
        }
        build(x);
        return;
    }
    for(int i = x + 1; i < y; i ++){
        s[i].s += k;
    }
    for(int i = l; i <= s[x].r; i ++){
        a[i] += k;
    }
    build(x);
    for(int i = s[y].l; i <= r; i ++){
        a[i] += k;
    }
    build(y);
    return;
}
signed main(){
    b = sqrt(n);
    for(int i = 1; i <= b; i ++){
        s[i].l = s[i - 1].r + 1, s[i].r = s[i].l + b - 1;
    }
    s[b].r = n;
    for(int i = 1; i <= b; i ++){
        for(int j = s[i].l; j <= s[i].r; j ++){
            belong[j] = i;
        }
    }
    for(int i = 1; i <= n; i ++){
        a[i] = mread();
        a[i] += a[i - 1];
    }
    for(int i = 1; i <= b; i ++){
        build(i);
    }
    q = mread();
    while(q --){
        int op = mread();
        if(op == 1){
            int l = mread(), r = mread();
            cout << query(l, r) << "\n";
        }
        else{
            int l = mread(), r = mread(), k = mread();
            add(l, r, k);
            if(r + 1 <= n){
                add2(r + 1, n, k * (r - l + 1));
            }
        }
    }
    return 0;
}