#include <bits/stdc++.h>
using namespace std;

int N, Q;
long long A[100005];  // A[1..N]: giá cổ phiếu từng ngày
vector<int> qs;       // các ngày bắt đầu T của từng truy vấn
const long long NEG = LLONG_MIN / 4;

// Bình bắt đầu từ ngày T. Mỗi ngày: mua 1 cổ phiếu, hoặc bán số lượng bất kỳ đang có, hoặc không làm gì.
// Lợi nhuận = tiền bán - tiền mua.

// Sub 1: quy hoạch động theo số cổ phiếu đang giữ. f[h] = lợi nhuận lớn nhất khi đang giữ đúng h cổ phiếu.
// Mỗi ngày: mua (h -> h+1) hoặc bán k cổ phiếu (h -> h-k). O(N^2) mỗi truy vấn. Dùng khi N <= 1000, Q <= 10.
long long solveDP(int T) {
    vector<long long> f(N + 2, NEG), g(N + 2, NEG);
    f[0] = 0;
    int maxH = 0;
    for (int j = T; j <= N; j++) {
        long long p = A[j];
        g = f;  // không làm gì
        for (int h = 0; h <= maxH; h++)  // mua 1 cổ phiếu
            if (f[h] > NEG) g[h + 1] = max(g[h + 1], f[h] - p);
        // bán xuống còn h cổ phiếu: g[h] = max theo h2 > h của f[h2] + (h2 - h) * p
        long long best = NEG;
        for (int h = maxH; h >= 0; h--) {
            if (best > NEG) g[h] = max(g[h], best - (long long)h * p);
            if (f[h] > NEG) best = max(best, f[h] + (long long)h * p);
        }
        f = g;
        maxH++;
    }
    long long ans = 0;
    for (int h = 0; h <= N + 1; h++) ans = max(ans, f[h]);
    return ans;
}

void sub1() {
    for (int T : qs) cout << solveDP(T) << "\n";
}

// Sub 2: tham lam bằng hàng đợi ưu tiên cho từng truy vấn (dùng khi Q <= 10). Mỗi ngày j thêm giá A[j] vào hàng đợi;
// nếu giá nhỏ nhất trong hàng đợi nhỏ hơn A[j] thì "bán" với lãi A[j] - giá đó rồi đẩy lại A[j]
// (để sau này có thể đổi ý bán ở ngày giá cao hơn). O(N log N) mỗi truy vấn.
long long solveHeap(int T) {
    priority_queue<long long, vector<long long>, greater<long long>> H;
    long long profit = 0;
    for (int j = T; j <= N; j++) {
        H.push(A[j]);
        while (!H.empty() && H.top() < A[j]) {
            profit += A[j] - H.top();
            H.pop();
            H.push(A[j]);
        }
    }
    return profit;
}

void sub2() {
    for (int T : qs) cout << solveHeap(T) << "\n";
}

// Sub 3: mỗi cổ phiếu mua ở ngày j nên bán ở ngày có giá cao nhất từ j về sau, nên mua 1 cổ phiếu mỗi ngày
// khi giá cao nhất về sau lớn hơn A[j]. Lãi của ngày j là mx[j] - A[j] với mx[j] = max(A[j..N]) (không phụ thuộc T).
// Đáp án truy vấn T = tổng các lãi từ ngày T đến N: tính sẵn tổng hậu tố, mỗi truy vấn O(1). Tổng O(N + Q).
void sub3() {
    vector<long long> suf(N + 2, 0);
    long long mx = 0;
    for (int j = N; j >= 1; j--) {
        mx = max(mx, A[j]);
        suf[j] = suf[j + 1] + (mx - A[j]);
    }
    for (int T : qs) cout << suf[T] << "\n";
}

int main() {
    freopen("vni.inp", "r", stdin);
    freopen("vni.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> A[i];
    cin >> Q;
    qs.resize(Q);
    for (auto &t : qs) cin >> t;
    if (N <= 1000 && Q <= 10) sub1();
    else if (Q <= 10) sub2();
    else sub3();
    return 0;
}