/*
  Author: EnderDeer
  Online Judge: Luogu
*/

#include<bits/stdc++.h>

#define int long long
#define mem(x) memset(x,0,sizeof(x))

using namespace std;

int read(){
   int s = 0,w = 1;
   char ch = getchar();
   while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
   while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
   return s * w;
}

int n,m;
int a[1000010];
int b[1000010];
int l[1000010],r[1000010];
int block,len;
int num[1000010];
int c[1000010];
int d[1000010];
int cnt;

void merge(int L, int R, int Mid){
    int i = L;int j = Mid + 1;int k = L;
    while(i <= Mid && j <= R){
        if(c[i] <= c[j])d[k ++] = c[i ++];
        else{
            cnt += Mid - i + 1;
            d[k ++] = c[j ++]; 
        }
    }
    while(i <= Mid)d[k ++] = c[i ++];
    while(j <= R)d[k ++] = c[j ++];
    for(i = L; i <= R; i ++)c[i] = d[i]; 
}

void mergesort(int L, int R){
    if(L < R){
        int Mid = (L + R) / 2;
        mergesort(L, Mid),mergesort(Mid + 1, R);
        merge(L, R, Mid);
    }
}

void swapp(int x,int y){
	if(a[x] > a[y])cnt --;
	if(a[y] > a[x])cnt ++;
	int posl = num[x];
	int posr = num[y];
	if(posl == posr){
		for(int i = x + 1;i <= y - 1;i ++){
			if(a[i] > a[x])cnt ++;
			if(a[i] < a[x])cnt --;
			if(a[i] < a[y])cnt ++;
			if(a[i] > a[y])cnt --;
		}
		return ;
	}
	for(int i = x + 1;i <= r[posl];i ++){
		if(a[i] > a[x])cnt ++;
		if(a[i] < a[x])cnt --;
		if(a[i] < a[y])cnt ++;
		if(a[i] > a[y])cnt --;
	}
	for(int i = posl + 1;i <= posr - 1;i ++){
		if(b[l[i]] < a[x]){
			int ll,rr,mid;
			ll = l[i],rr = r[i];
			while(ll != rr){
				mid = (ll + rr) / 2;
				if(b[mid] < a[x])ll = mid + 1;
				else rr = mid;
			}
			if(ll >= l[i] && b[ll] >= a[x])ll --;
			cnt -= ll - l[i] + 1;
		}
		if(b[r[i]] > a[x]){
			int ll,rr,mid;
			ll = l[i],rr = r[i];
			while(ll != rr){
				mid = (ll + rr) / 2;
				if(b[mid] <= a[x])ll = mid + 1;
				else rr = mid;
			}
			cnt += r[i] - rr + 1;
		}
		if(b[l[i]] < a[y]){
			int ll,rr,mid;
			ll = l[i],rr = r[i];
			while(ll != rr){
				mid = (ll + rr) / 2;
				if(b[mid] < a[y])ll = mid + 1;
				else rr = mid;
			}
			if(ll >= l[i] && b[ll] >= a[y])ll --;
			cnt += ll - l[i] + 1;
		}
		if(b[r[i]] < a[y]){
			int ll,rr,mid;
			ll = l[i],rr = r[i];
			while(ll != rr){
				mid = (ll + rr) / 2;
				if(b[mid] <= a[y])ll = mid + 1;
				else rr = mid;
			}
			cnt -= r[i] - rr + 1;
		}
	}
	for(int i = l[posr];i <= y - 1;i ++){
		if(a[i] > a[x])cnt ++;
		if(a[i] < a[x])cnt --;
		if(a[i] < a[y])cnt ++;
		if(a[i] > a[y])cnt --;
	}
	swap(a[x],a[y]);
	b[x] = a[x];
	b[y] = a[y];
	sort(b + l[num[x]],b + r[num[x]] + 1);
	sort(b + l[num[y]],b + r[num[y]] + 1);
}

signed main(){
	cin>>n;
	block = sqrt(n);
	len = ceil(n * 1.0 / block);
	for(int i = 1;i <= len;i ++){
		l[i] = (i - 1) * block + 1;
		r[i] = i * block;
	}
	r[len] = n;
	for(int i = 1;i <= n;i ++){
		a[i] = read();
		b[i] = a[i];
		c[i] = b[i];
		num[i] = (i - 1) / block + 1;
	}
	for(int i = 1;i <= len;i ++)sort(b + l[i],b + r[i] + 1);
	mergesort(1,n);
	cout<<cnt<<endl;
	cin>>m;
	while(m --){
		int x,y;
		x = read(),y = read();
		if(x > y)swap(x,y);
		if(a[x] == a[y]){
			cout<<cnt<<endl;
			continue;
		}
		swapp(x,y);
		cout<<cnt<<endl;
	}
	return 0;
}