#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 = 3e5 + 10, M = 1010, inf = 0x3f3f3f3f, mod = 1e9 + 7, P = 13331;
int n;
int a[N], b[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 = 1e9;
    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;
}
int c[N];
void solve()
{
    int ans = 0;
    cin >> n;
    build(1, 1, n + 10);
    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;
    for (int i = lst; i >= 1; i--)
    {
        if (b[i] > s)
        {
            ans += i * (b[i] - s);
            for (int j = s; j < b[i]; j++)
                st.insert(i);
        }
        if (a[i] - b[i] > 0)
            modify(1, i, i, a[i] - b[i]);
        s = b[i];
    }

    for (int i = lst + 1; i <= n; i++)
    {
        if (a[i])
            modify(1, i, i, a[i]);
    }
    cout << ans << endl;
    int q;
    cin >> q;
    st.insert(0);
    while (q--)
    {
        int op, x;
        cin >> op >> x;
        x++;
        if (op == 1)
        {
            if (x == 1)
            {
                if (ask(1, 2, 2) == 0)
                {
                    ans++;
                    st.insert(1);
                }
                else
                {
                    int l = 0, r = 2e5 + 10;
                    while (l < r)
                    {
                        int mid = l + r + 1 >> 1;
                        if (ask(1, x + 1, x + mid + 1))
                            l = mid;
                        else
                            r = mid - 1;
                    }
                    ans += r + 2;
                    modify(1, x + 1, x + 1 + r, -1);
                    st.insert(x + r + 1);
                }
            }
            else
            {
                if (st.find(x - 1) != st.end())
                {
                    int l = 0, r = 2e5 + 10;
                    while (l < r)
                    {
                        int mid = l + r + 1 >> 1;
                        if (ask(1, x + 1, x + 1 + mid))
                            l = mid;
                        else
                            r = mid - 1;
                    }

                    if (ask(1, x + 1, x + 1))
                    {
                        ans += r + 2;
                        modify(1, x + 1, x + 1 + r, -1);
                        st.erase(st.find(x - 1));
                        st.insert(x + r + 1);
                    }
                    else
                    {
                        ans += 2;
                        st.erase(st.find(x - 1));
                        st.insert(x);
                    }
                }
                else
                {
                    modify(1, x, x, 1);
                }
            }
        }
        else
        {

            if (ask(1, x, x))
            {

                modify(1, x, x, -1);
            }
            else
            {

                auto it = st.lower_bound(x);
                // if (q <= 2)
                //     cout << "---" << *it << endl;
                st.erase(it);
                st.insert(x - 1);
                int now = *it;
                ans -= now;
                ans += x - 1;

                if (x + 1 <= now)
                    modify(1, x + 1, now, 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;
}