#include "bits/stdc++.h"
using namespace std;
struct trnode{
	trnode* left;
	trnode* right;
	int val;
	int pri;
	int siz;
	trnode(int _val){
		val = _val;
		pri = rand();
		siz = 1;
		left = NULL;
		right = NULL;
	}
};
typedef trnode* pnode;
struct treap{
	pnode root;
	treap(){
		root = NULL;
	}
	int size(pnode tree){
		if(tree){
			return tree -> siz;
		}
		return 0;
	}
	void upd(pnode &tree){
		if(tree){
			tree -> siz = size(tree -> left) + 1 + size(tree -> right);
		}
	}
	void split(pnode tree , pnode &l , pnode &r , int key){
		if(!tree){
			l = NULL;
			r = NULL;
		}
		else if(tree -> val <= key){
			split(tree -> right , tree -> right , r , key);
			l = tree;
		}
		else{
			split(tree -> left , l , tree -> left , key);
			r = tree;
		}
		upd(tree);
	}
	void merge(pnode &tree , pnode l , pnode r){
		if(!l || !r){
			tree = l ? l : r;
		}
		else if(l -> pri > r -> pri){
			merge(l -> right , l -> right , r);
			tree = l;
		}
		else{
			merge(r -> left , l , r -> left);
			tree = r;
		}
		upd(tree);
	}
	void insert(pnode &tree , pnode key){
		if(!tree){
			tree = key;
		}
		else if(tree -> pri < key -> pri){
			split(tree , key -> left , key -> right , key -> val);
			tree = key;
		}
		else if(tree -> val >= key -> val){
			insert(tree -> left , key);
		}
		else{
			insert(tree -> right , key);
		}
		upd(tree);
	}
	void erase(pnode &tree , int key){
		if(!tree){
			return;
		}
		else if(tree -> val == key){
			merge(tree , tree -> left , tree -> right);
		}
		else if(tree -> val > key){
			erase(tree -> left , key);
		}
		else{
			erase(tree -> right , key);
		}
		upd(tree);
	}
	void erase(int key){
		erase(root , key);
	}
	void insert(int key){
		insert(root , new trnode(key));
	}
	int range(int l , int r){
		pnode L = NULL;
		pnode R = NULL;
		pnode X = NULL;
		pnode Y = NULL;
		split(root , L , R , r);
		split(L , X , Y , l - 1);
		int ret = size(Y);
		merge(L , X , Y);
		merge(root , L , R);
		return ret;
	}
};
const int N = 2.5e5 + 5;
const int M = 5e4 + 5;
const int LN = 15;
int n;
int arr[N];
int q;
int x , y;
long long inv = 0;
struct node{
    treap indices;
    int left;
    int right;
    node(){
        left = -1;
        right = -1;
    }
};
struct TRIE{
	node nodes[(N + 10001) * LN];
    int cur;
    TRIE(){
        cur = 0;
    }
    void insert(int num ,int index){
    	int nd = 0;
        for(int i = LN ; i >= 0 ; --i){
            bool b = (num >> i) & 1;
            if(b){
                if(nodes[nd].right == -1){
                    nodes[nd].right = ++cur;
                }
                nd = nodes[nd].right;
                nodes[nd].indices.insert(index);
            }
            else{
                if(nodes[nd].left == -1){
                    nodes[nd].left = ++cur;
                }
                nd = nodes[nd].left;
                nodes[nd].indices.insert(index);
            }
        }
    }
    void erase(int num , int index){
        int nd = 0;
        for(int i = LN ; i >= 0 ; --i){
            bool b = (num >> i) & 1;
            if(b){
                nd = nodes[nd].right;
            }
            else{
                nd = nodes[nd].left;
            }
            nodes[nd].indices.erase(index);
        }
    }
    void update(int index , int value){
    	erase(arr[index] , index);
    	arr[index] = value;
    	insert(arr[index] , index);
    }
    int get(int l , int r , int k){
        ++k;
        int ret = 0;
        int nd = 0;
        for(int i = LN ; i >= 0 && nd >= 0; --i){
            bool b = (k >> i) & 1;
            if(b){
                int z = 0;
                if(nodes[nd].left != -1){
                	z = nodes[nodes[nd].left].indices.range(l , r);
                }
                ret += z;
                nd = nodes[nd].right;
            }
            else{
                nd = nodes[nd].left;
            }
        }
        return ret;
    }
};
TRIE trie;
int main(){
	scanf("%d" , &n);
	for(int i = 1 ; i <= n ; ++i){
		scanf("%d" , arr + i);
		trie.insert(arr[i] , i);
	}
	for(int i = n ; i >= 1 ; --i){
		inv += trie.get(i + 1 , n , arr[i] - 1);
	}
	scanf("%d" , &q);
	while(q--){
		scanf("%d %d" , &x , &y);
		inv -= x - 1 - trie.get(1 , x - 1 , arr[x]);
		inv -= trie.get(x + 1 , n , arr[x] - 1);
		trie.update(x , y);
		inv += x - 1 - trie.get(1 , x - 1 , arr[x]);
		inv += trie.get(x + 1 , n , arr[x] - 1);
		printf("%lld\n" , inv);
	}
}