#include <cstdio>
#include <algorithm>
#define ls (rt << 1)
#define rs (rt << 1 | 1)

using namespace std;
const int N = 3e5 + 5;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c < '0' || c > '9'; c = getchar())
        if (c == '-') f = -1;
    for (; c >='0' && c <='9'; c = getchar())
        x = x * 10 + c - '0';
    return x * f;
}

int n, m, s[N], b[N], sa[N], rk[N];
int t1[N*4], tag1[N*4], t2[N*4], tag2[N*4];

struct Ques {
    int l, r, k;
}q[N];

bool Cmp(const int &x, const int &y) {
    return q[x].l < q[y].l;
}

void Build1(int rt, int l, int r) {
    if (l == r) return t1[rt] = -s[q[sa[l]].l-1], void();
    int mid = l + r >> 1;
    Build1(ls, l, mid); Build1(rs, mid+1, r);
    t1[rt] = min(t1[ls], t1[rs]);
}

void Pushdown1(int rt) {
    int x = tag1[rt]; tag1[rt] = 0;
    t1[ls] += x; tag1[ls] += x; t1[rs] += x; tag1[rs] += x;
}

void Add1(int rt, int l, int r, int x, int w) {
    if (x <= l) return t1[rt] += w, tag1[rt] += w, void();
    if (tag1[rt]) Pushdown1(rt);
    int mid = l + r >> 1;
    if (x <= mid) Add1(ls, l, mid, x, w);
    Add1(rs, mid + 1, r, x, w);
    t1[rt] = min(t1[ls], t1[rs]);
}

int Ask1(int rt, int l, int r, int x, int y) {//min
    if (x <= l && r <= y) return t1[rt];
    if (tag1[rt]) Pushdown1(rt);
    int mid = l + r >> 1, ans = 2e9;
    if (x <= mid) ans = Ask1(ls, l, mid, x, y);
    if (y > mid) ans = min(ans, Ask1(rs, mid+1, r, x, y));
    return ans;
}

void Build2(int rt, int l, int r) {
    if (l == r) return t2[rt] = -s[q[sa[l]].r], void();
    int mid = l + r >> 1;
    Build2(ls, l, mid); Build2(rs, mid+1, r);
    t2[rt] = max(t2[ls], t2[rs]);
}

void Pushdown2(int rt) {
    int x = tag2[rt]; tag2[rt] = 0;
    t2[ls] += x; tag2[ls] += x; t2[rs] += x; tag2[rs] += x;
}

void Add2(int rt, int l, int r, int x, int w) {
    if (x <= l) return t2[rt] += w, tag2[rt] += w, void();
    if (tag2[rt]) Pushdown2(rt);
    int mid = l + r >> 1;
    if (x <= mid) Add2(ls, l, mid, x, w);
    Add2(rs, mid + 1, r, x, w);
    t2[rt] = max(t2[ls], t2[rs]);
}

int Ask2(int rt, int l, int r, int x, int y) {//min
    if (x <= l && r <= y) return t2[rt];
    if (tag2[rt]) Pushdown2(rt);
    int mid = l + r >> 1, ans = -2e9;
    if (x <= mid) ans = Ask2(ls, l, mid, x, y);
    if (y > mid) ans = max(ans, Ask2(rs, mid+1, r, x, y));
    return ans;
}

int main() {
    n = read();
    for (int i = 1; i <= n; ++i) s[i] = read();
    m = read();
    for (int i = 1; i <= m; ++i) {
        int l = read(), r = read();
        q[i] = (Ques) {l, r, read()};
        b[l]++, b[r+1]--; sa[i] = i;
    }
    sort(sa + 1, sa + m + 1, Cmp);
    for (int i = 1; i <= m; ++i)
        rk[sa[i]] = i;
    for (int i = 1, sum = 0; i <= n; ++i)
        s[i] = s[i-1] + ((sum += b[i]) ? s[i] : 0);
    Build1(1, 1, m); Build2(1, 1, m);
    for (int i = 1; i <= m; ++i) {
        int x = rk[i], k = min(q[i].k, Ask1(1, 1, m, 1, x) - Ask2(1, 1, m, x, m));
        Add1(1, 1, m, x + 1, k); Add2(1, 1, m, x, k);
        printf("%d
", k);
    }
    return 0;
}