#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>


typedef long long ll;
typedef long double ld;

using namespace std;
const int MAXN = 310000;
const int SQ = 1000;
int n, m;
int a[MAXN];
int q;
int bbc[MAXN];
int bb[2 * SQ][2 * SQ];
ll sm[2 * SQ][2 * SQ];

void rebuild(int k) {
	int l = k * SQ;
	int r = min((k + 1) * SQ, n);
	bbc[k] = 0;
	int now = a[l];
	bb[k][bbc[k]++] = l;
	for (int i = l + 1; i < r; ++i)
		if (a[i] > now)
			now = a[i], bb[k][bbc[k]++] = i;
	ll sum = 0;
	for (int i = bbc[k] - 1; i > 0; --i)
		sum += (ll)(bb[k][i] - l) * (a[bb[k][i]] - a[bb[k][i - 1]]), sm[k][i - 1] = sum;
	sm[k][bbc[k] - 1] = 0;
}

bool cmp(int x, int y) {
	return a[x] < y;
}

pair<int, ll> get(int now, int k) {
	int l = k * SQ;
	int r = min((k + 1) * SQ, n);
	int mx = a[bb[k][bbc[k] - 1]];
	if (now >= mx)
		return make_pair(now, (ll)(r - l) * (m - now));
	int x = lower_bound(bb[k], bb[k] + bbc[k], now, cmp) - bb[k];
	ll sum = (ll)(r - l) * (m - mx) + sm[k][x] + (ll)(a[bb[k][x]] - now) * (bb[k][x] - l);
	return make_pair(mx, sum);
}

int main() {
	int gr;
	scanf("%d", &gr);
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
		scanf("%d", a + i);
	for (int i = 0; i * SQ < n; ++i)
		rebuild(i);

	scanf("%d", &q);
	for (int i = -1; i < q; ++i) {
		int x, y;
		if (i != -1) {
			scanf("%d%d", &x, &y);
			--x;
			a[x] = y;
			rebuild(x / SQ);
		}
		int now = 0;
		ll sum = 0;
		for (int j = 0; j * SQ < n; ++j) {
			pair<int, ll> aa = get(now, j);
			sum += aa.second;
			now = aa.first;
		}
		printf("%lld ", sum);
	}
	printf("\n");
	return 0;
}


