#include <bits/stdc++.h>
using namespace std;
// typedef long long lld;
#define int long long
const int N = 100005;

struct SGT {
    int d[N << 2], b[N << 2], v[N << 2], n;

    void build(int s, int t, int p, int *a) {
        // 对 [s,t] 区间建立线段树,当前根的编号为 p
        if (s == t) {
            d[p] = a[s];
            return;
        }
        int m = s + ((t - s) >> 1);
        // 移位运算符的优先级小于加减法，所以加上括号
        // 如果写成 (s + t) >> 1 可能会超出 int 范围
        build(s, m, p * 2, a), build(m + 1, t, p * 2 + 1, a);
        // 递归对左右区间建树
        d[p] = d[p * 2] + d[(p * 2) + 1];
    }
    void update(int l, int r, int c, int s, int t, int p) {
        if (l <= s && t <= r) {
            d[p] = (t - s + 1) * c, b[p] = c, v[p] = 1;
            return;
        }
        int m = s + ((t - s) >> 1);
        // 额外数组储存是否修改值
        if (v[p]) {
            d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
            b[p * 2] = b[p * 2 + 1] = b[p];
            v[p * 2] = v[p * 2 + 1] = 1;
            v[p] = 0;
        }
        if (l <= m) update(l, r, c, s, m, p * 2);
        if (r > m) update(l, r, c, m + 1, t, p * 2 + 1);
        d[p] = d[p * 2] + d[p * 2 + 1];
    }

    int getsum(int l, int r, int s, int t, int p) {
        if (l <= s && t <= r) return d[p];
        int m = s + ((t - s) >> 1);
        if (v[p]) {
            d[p * 2] = b[p] * (m - s + 1), d[p * 2 + 1] = b[p] * (t - m);
            b[p * 2] = b[p * 2 + 1] = b[p];
            v[p * 2] = v[p * 2 + 1] = 1;
            v[p] = 0;
        }
        int sum = 0;
        if (l <= m) sum = getsum(l, r, s, m, p * 2);
        if (r > m) sum += getsum(l, r, m + 1, t, p * 2 + 1);
        return sum;
    }
    int getpos(int x) {
        if(x == 1) {
            return getsum(1, 1, 1, n, 1);
        } else {
            return getsum(1, x, 1, n, 1) - getsum(1, x - 1, 1, n, 1);
        }
    }
    int sum() {
        return getsum(1, n, 1, n, 1);
    }
    void clear() {
        for(int i = 0; i < n * 4 + 1; i++) {
            d[i] = b[i] = v[i] = 0;
        }
        n = 0;
    }

};

int find(int x, int flg, SGT &T) {
    // if(x == T.n) return x;
    int l = x + 1, r = T.n;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(T.getpos(mid) > flg) {
            r = mid - 1;
        }  else {
            l = mid;
        }
    }
    // if(l == T.n && T.getpos(T.n) <= flg) {
    //     return T.n;
    // }
    if(T.getpos(r) > flg) return r - 1;
    return r;
}
SGT F, G;
int f[N], g[N];
int a[N], suma = 0, maxa = 0; 
void solve() {
    int n; cin >> n;
    suma = 0, maxa = 0;
    for(int i = 1; i <= n; i++) {
        cin >> a[i]; 
        suma += a[i]; maxa = max(maxa, a[i]);
    }
    f[0] = 0;
    for(int i = 1; i <= n; i++) {
        f[i] = max(f[i - 1], a[i]);
    }
    g[n + 1] = 0;
    for(int j = n; j >= 1; j--) {
        g[j] = max(g[j + 1], a[j]);
    }
    reverse(g + 1, g + 1 + n);
    F.n = n; G.n = n;
    F.build(1, n, 1, f); G.build(1, n, 1, g);
    int q; cin >> q;
    while(q--) {
        int x, v; cin >> x >> v;
        suma += v;
        maxa = max(maxa, a[x] + v);
        a[x] += v;
        int nxt = 0;
        if(a[x] > F.getpos(x)) {
            nxt = find(x, a[x], F);
            F.update(x, nxt, a[x], 1, n, 1);
        }
        if(a[x] > G.getpos(n - x + 1)) {
            nxt = find(n - x + 1, a[x], G);
            G.update(n - x + 1, nxt, a[x], 1, n, 1);
        }
        // cout << "FSUM : " << F.sum() << " GSUM : " << G.sum() << "\n";
        cout << F.sum() + G.sum() - n * maxa - suma << "\n";
        // for(int i = 1; i <= n; i++) {
        //     cout << F.getpos(i) << " ";
        // }
        // cout << "\n";
    }
    F.clear(); G.clear();
}

signed main() {
    // freopen("data.in", "r", stdin);
    // freopen("data.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T; cin >> T; 
    while(T--) solve();
    return 0;
}