#include <bits/stdc++.h>
int c[200002];
int merge(int i, int j, int *s, int x, int y, int count) {
  if (i == j && s[i] == x) {
    s[i] = y;
    return count + 1;
  } else if (i != j) {
    int count1 = merge(i, (i + j) / 2, s, x, y, count);
    int count2 = merge((i + j) / 2 + 1, j, s, x, y, count);
    int a = i, b = (i + j) / 2 + 1;
    int d;
    for (d = i; d <= j; d++) {
      if ((i + j) / 2 < a) {
        c[d] = s[b];
        b++;
      } else if (j < b) {
        c[d] = s[a];
        a++;
      } else if (s[a] < s[b]) {
        c[d] = s[a];
        a++;
      } else {
        c[d] = s[b];
        b++;
      }
    }
    for (d = i; d <= j; d++) s[d] = c[d];
    return count1 + count2;
  }
  return 0;
}
int main() {
  int n;
  scanf("%d", &n);
  int a[n + 1], i;
  for (i = 0; i < n; i++) scanf("%d", &a[i]);
  int q;
  scanf("%d", &q);
  int x[q + 1], y[q + 1];
  long sum = 0;
  for (i = 0; i < n; i++) sum += (long)a[i];
  for (i = 0; i < q; i++) scanf("%d%d", &x[i], &y[i]);
  for (i = 0; i < q; i++) {
    int count = 0;
    count = merge(0, n - 1, a, x[i], y[i], count);
    long plus = (long)y[i] - (long)x[i];
    plus *= (long)count;
    sum += plus;
    printf("%ld\n", sum);
  }
  return 0;
}
