#include <iostream>
#include <set>
#include <vector>
using namespace std;
#define int long long
const int mn = 2e6+5;
set<int> indxs[mn];
signed main() {
	int n; cin >> n;
	vector<int> h(n+1);
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		indxs[h[i]].insert(i);
	}
	h[n] = -1;
	int tot = 0;
	int cur = 1e9;
	set<int> mins;
	mins.insert(n);
	for (int i = 0; i < n; i++) {
		if (h[i] < cur) {
			mins.insert(i);
			cur = h[i];
		}
		tot += cur;
	}
	cout << tot << endl;
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int p, v; cin >> p >> v;
		if (p == 2) p = -1;
		int nex = *mins.upper_bound(v);
		if (mins.count(v)) {
			if (p == 1) {
				auto fuckingshit = indxs[h[v]].upper_bound(v);
				if (fuckingshit != indxs[h[v]].end() && *fuckingshit < nex) {
					nex = *fuckingshit;
					mins.insert(nex);
				}
			}
			tot += p*(nex-v);
		}

		if (h[v]+p <= h[nex]) {
			if (mins.count(v) == 0) tot += p*(nex-v);
			mins.erase(nex);
			mins.insert(v);
		}
		else if (v != 0 && mins.count(v) && h[v] + p >= h[*prev(mins.lower_bound(v))]) {
			mins.erase(v);
		}
		else if (v != 0 && mins.count(v) == 0 && h[v]+p < h[*prev(mins.lower_bound(v))]) {
			mins.insert(v);
			tot -= nex-v;
		}
		indxs[h[v]].erase(v);
		h[v] += p;
		indxs[h[v]].insert(v);
		/*for (int j : h) cout << j << ' ';
		cout << endl;
		for (int j : mins) cout << j << ' ';
		cout << endl;*/
		cout << tot << endl;
	}
}