#include <bits/stdc++.h>
using namespace std;
#define xx first
#define yy second
#define endl "\n"
#define pb push_back
#define int long long
#define ll long long
#define lowbit(x) x & (-x)
typedef pair<int, int> pii;
#define LF(x) fixed << setprecision(x)
#define Yshanqian ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
const int N = 1e6 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
int n;
int a[N], b[N], cnt[N];
multiset<int> st;
struct node
{
    int l, r;
    int mn, lazy;
} tr[N << 2];
void pushup(int u)
{
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
}
void build(int u, int l, int r)
{
    tr[u] = {l, r, 0, 0};
    if (l == r)
        return;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}
void change(int u, int x)
{
    tr[u].mn += x;
    tr[u].lazy += x;
}
void pushdown(int u)
{
    if (tr[u].lazy)
    {
        change(u << 1, tr[u].lazy);
        change(u << 1 | 1, tr[u].lazy);
        tr[u].lazy = 0;
    }
}
void modify(int u, int l, int r, int x)
{
    if (tr[u].l >= l && tr[u].r <= r)
    {
        change(u, x);
        return;
    }
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid)
        modify(u << 1, l, r, x);
    if (r > mid)
        modify(u << 1 | 1, l, r, x);
    pushup(u);
}
int ask(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].mn;
    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    int ans = inf;
    if (l <= mid)
        ans = min(ans, ask(u << 1, l, r));
    if (r > mid)
        ans = min(ans, ask(u << 1 | 1, l, r));
    return ans;
}
void solve()
{
    int ans = 0;
    cin >> n;
    build(1, 1, 1e6);
    int mn = inf;
    b[0] = inf;
    int lst = -1;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = min(b[i - 1], a[i]);
        if (b[i] != 0)
            lst = i;
    }
    int s = 0;
    int pre = 0;
    for (int i = lst; i >= 1; i--)
    {
        if (b[i] != pre)
        {
            for (int j = 1; j <= b[i] - s; j++)
                st.insert(i), ans += i, cnt[i]++;
            pre = b[i], s += b[i] - s;
        }

        for (int j = 1; j <= a[i] - pre; j++)
            modify(1, i, i, 1);

        // cout << s << "----\n";
    }

    for (int i = lst + 1; i <= n; i++)
    {
        if (a[i])
            modify(1, i, i, a[i]);
    }

    cout << ans << endl;

    st.insert(0);
    int q;
    cin >> q;
    while (q--)
    {
        int op, x;
        cin >> op >> x;
        x++;

        if (op == 1) // 加一个数
        {
            if (st.find(x - 1) != st.end())
            {
                int l = 1, r = 2e5 + 10;
                while (l < r)
                {
                    int mid = l + r + 1 >> 1;
                    if (ask(1, x + 1, x + mid))
                        l = mid;
                    else
                        r = mid - 1;
                }
                if (ask(1, x + 1, x + 1))
                {
                    ans += r + 1;
                    modify(1, x + 1, x + r, -1);
                    st.insert(x + r);
                }
                else
                {
                    ans++;
                    st.insert(x);
                }
                if (x - 1 != 0)
                    st.erase(st.find(x - 1));
            }
            else
                modify(1, x, x, 1);
        }
        else
        {
            if (ask(1, x, x))
                modify(1, x, x, -1);
            else
            {
                auto it = st.lower_bound(x);
                int now = *it;
                ans -= now - x + 1;
                if (x != now)
                    modify(1, x + 1, now, 1);
                st.erase(it);
                st.insert(x - 1);
            }
        }
        cout << ans << endl;
    }
}
signed main()
{
    Yshanqian;
    int T;
    T = 1;
    // cin >> T;
    for (int cases = 1; cases <= T; ++cases)
    {
        // cout<<"Case #"<<cases<<": ";
        solve();
    }
    return 0;
}