#include <bits/stdc++.h>
using namespace std;
int main() {
  int N{0};
  cin >> N;
  int arr[N];
  pair<int, int> p;
  long long ksum{0};
  int q;
  for (int i = 0; i < N; i++) {
    cin >> arr[i];
  }
  cin >> q;
  int b = 0;
  int c = 0;
  int len = sizeof(arr) / sizeof(arr[0]);
  while (q--) {
    cin >> b >> c;
    replace(arr, arr + len, b, c);
    for (int c = 0; c < N; c++) {
      ksum += arr[c];
      if (ksum > 1e9) {
        ksum = ksum % 1000000009;
      }
    }
    cout << ksum;
    ksum -= ksum;
  }
}
