#include <bits/stdc++.h>
     
    using namespace std;
     
    int a[250006], n, s_size,m;
    pair<long long, long long> pr;
    long long sum = 0; 
    vector<int> sq[506];
     
    inline void init() {
        s_size = ceil(sqrt(n));
        sq[0].push_back(a[0]);
        for (int i = 1; i < n; i++) {
            sq[i / s_size].push_back(a[i]);
        }
        for (int i = 0; i < s_size; i++) {
            sort(sq[i].begin(), sq[i].end());
        }
    }
     
    inline void update(int index, int val) {
        int sindex = index / s_size;
        vector<int>& v = sq[sindex];
        vector<int>::iterator it = lower_bound(v.begin(), v.end(), a[index]);
        v.erase(it);
        it = upper_bound(v.begin(), v.end(), val);
        v.insert(it, val);
        a[index] = val;
    }
     
    inline int between(vector<int>& v, int s, int e) {
        return upper_bound(v.begin(), v.end(), e) - lower_bound(v.begin(), v.end(), s);
    }
     
    inline void between(int index, int s, int e) {
        pr.first = 0;
        pr.second = 0;
        int ee = ((s_size + index) / s_size) * s_size;
        int ss = (index / s_size) * s_size;
        for (int i = ss; i < index; i++) {
            if (a[i] > s && a[i] <= e)
                pr.first++;
        }
        for (int i = index + 1; i < ee; i++) {
            if (a[i] >= s && a[i] < e)
                pr.second++;
        }
        ss = (index / s_size);
        for (int i = 0; i < ss; i++) {
            pr.first += between(sq[i], s + 1, e);
        }
        for (int i = ss + 1; i < s_size; i++) {
            pr.second += between(sq[i], s, e - 1);
        }
    }
     
    struct trie_nod {
        trie_nod* t[2];
        long long c[2];
     
        trie_nod() {
            t[0] = t[1] = NULL;
            c[0] = c[1] = 0;
        }
    };
     
    struct trie {
        trie_nod* root = new trie_nod();
     
        int insert(int x) {
            bool index;
            long long cnt = 0;
            trie_nod* curr = root;
            for (int i = 16; i >= 0; i--) {
                index = (((1 << i) & x) != 0);
                if(!index)
                    cnt += curr->c[1];
                curr->c[index]++;
                if (curr->t[index] == NULL)
                    curr->t[index] = new trie_nod();
                curr = curr->t[index];
            }   
            return cnt;
        }
    };
     
    int main() {
        trie tr;
        scanf("%d", &n);
        sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            sum += tr.insert(a[i]);
        }
        init();
        scanf("%d", &m);
        while (m--) {
            int x, y;
            scanf("%d%d", &x, &y);
            x--;
            if (a[x] < y) {
                between(x, a[x], y);
                sum -= pr.first;
                sum += pr.second;
                update(x, y);
            } else if (a[x] > y) {
                between(x, y, a[x]);
                sum += pr.first;
                sum -= pr.second;
                update(x, y);
            }
            printf("%lld\n", sum);
        }
        return 0;
    }