#include <bits/stdc++.h>

 using namespace std;

 #define N 20005

 struct Node{

     int l , r , val , sz , pri , cnt;

     //cnt表示当前位置相同的数有多少个，pri表示优先级，sz表示这棵子树所含有的节点总个数

     Node(){

         l = r = ;

         cnt = sz =  , pri = rand();

         val = ;

     }

     Node(int v){

         Node();

         val = v;

     }

 };

 #define ls node[x].l

 #define rs node[x].r

 namespace Treap{

     int tot;//Treap Node节点的总个数

     int A[N];//有n棵treap树，A[]表示每棵treap树的起始位置

     Node node[N*];

     void init(){

         node[] = Node();

         node[].cnt = node[].sz = ;

         memset(A ,  , sizeof(A));

         tot = ;

     }

     int newNode(int v){

         ++tot;

         node[tot].cnt = node[tot].sz = ;

         node[tot].l = node[tot].r = ;

         node[tot].pri = rand();

         node[tot].val = v;

         return tot;

     }

     void push_up(int x) {

        // cout<<"here: "<<x<<" "<<ls<<" "<<rs<<endl;

         if(x>)

             node[x].sz = node[ls].sz+node[rs].sz+node[x].cnt;

     }

     void rotL(int &x){

         int y = rs;

         rs = node[y].l;

         node[y].l = x;

         push_up(x);

         push_up(y);

         x = y;

     }

     void rotR(int &x){

         int y = ls;

         ls = node[y].r;

         node[y].r = x;

         push_up(x);

         push_up(y);

         x = y;

     }

     void insert(int &x , int v){

     //    cout<<x<<" "<<v<<endl;

         if(x == ) x = newNode(v);

         else if(node[x].val>v){

             insert(ls , v);

             if(node[ls].pri>node[x].pri) rotR(x);

         }

         else if(node[x].val<v){

             insert(rs , v);

             if(node[rs].pri>node[x].pri) rotL(x);

         }

         else node[x].cnt++;

         push_up(x);

        // cout<<x<<" "<<v<<" "<<"endd"<<endl;

     }

     void erase(int &x , int v){

         if(x == ) return ;

         else if(v<node[x].val) erase(ls , v);

         else if(v>node[x].val) erase(rs , v);

         else {

             node[x].cnt--;

             if(node[x].cnt<=){

                 if(ls==&&rs==) x = ;

                 else if(ls == ) x = rs;

                 else if(rs == ) x = ls;

                 else{

                     if(node[ls].pri <node[rs].pri) rotL(x),erase(ls,v);

                     else rotR(x) , erase(rs , v);

                 }

             }

         }

         push_up(x);

     }

     int getCnt(int x , int v){//从x号节点出发找到对应的子树下小于等于v的值的个数

         if(x == ) return ;

         int ans = ;

         if(node[x].val>v) ans = getCnt(ls , v);

         else if(node[x].val<v) ans = node[x].cnt+node[ls].sz+getCnt(rs , v);

         else ans = node[x].cnt+node[ls].sz;

         return ans;

     }

 }

 int n , m , h[N] , a[N] , tot;

 //树状数组部分

 #define lowbit(x) x&(-x)

 void Add(int id , int v)

 {

     for(int x=id ; x<=n ; x+=lowbit(x)){

         Treap::insert(Treap::A[x] , v);

     }

 }

 void Erase(int id , int v)

 {

     for(int x=id ; x<=n ; x+=lowbit(x)){

         Treap::erase(Treap::A[x] , v);

     }

 }

 int getSum(int p , int v)//cal 1~p区间内小于等于v的值的个数

 {

     int sum = ;

     for(int x=p ; x> ; x-=lowbit(x)){

         sum+=Treap::getCnt(Treap::A[x] , v);

     }

     return sum;

 }

 int getSumMin(int p , int v)//cal 1~p区间内小于v的值的个数

 {

     v--;//important保证等于的情况被排除

     return getSum(p , v);

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     scanf("%d" , &n);

     for(int i= ; i<=n ; i++){

         scanf("%d" , &h[i]);

         a[i] =  h[i];

     }

     sort(a+ , a+n+);

     tot = unique(a+ , a+n+)-(a+);

     Treap::init();

     int sum = ;

     for(int i= ; i<=n ; i++){

         h[i] = lower_bound(a+ , a+tot+ , h[i])-a;

         Add(i , h[i]);

         sum+=i--getSum(i- , h[i]);

     }

     printf("%d\n" , sum);

     scanf("%d" , &m);

     while(m--){

 //        for(int i=1 ; i<=n ; i++)

 //            cout<<h[i]<<" ";

 //        cout<<endl;

         int ai , bi;

         scanf("%d%d" , &ai , &bi);

         if(ai>bi) swap(ai , bi);

         if(h[ai]<h[bi]) sum++;

         else if(h[ai]>h[bi]) sum--;

         else{

             printf("%d\n" , sum);

             continue;

         }

         int add = ;

         if(bi-ai>){

             add += getSumMin(bi- , h[bi])-getSumMin(ai , h[bi]);

             add -= (bi-ai-)-(getSum(bi- , h[bi])-getSum(ai , h[bi]));

             add += (bi-ai-)-(getSum(bi- , h[ai])-getSum(ai , h[ai]));

             add -= getSumMin(bi- , h[ai])-getSumMin(ai , h[ai]);

         }

         sum += add;

         Erase(ai , h[ai]);

         Erase(bi , h[bi]);

         Add(ai , h[bi]);

         Add(bi , h[ai]);

         swap(h[ai] , h[bi]);

         printf("%d\n" , sum);

     }

     return ;

 }