#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
template<typename T>
inline T  max(T &a, T &b) {
	return a > b ? a : b;
}
template<typename T>
inline T  min(T &a, T &b) {
	return a < b ? a : b;
}

inline char gt() {
	static char buf[1 << 21], *p1 = buf, *p2 = buf;
	return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void  read(T &x) {
	register char ch = gt();
	x = 0;
	int w(0);
	while(!(ch >= '0' && ch <= '9'))w |= ch == '-', ch = gt();
	while(ch >= '0' && ch <= '9')x = x * 10 + (ch & 15), ch = gt();
	w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
	if(x < 0) x = -x, putchar('-');
	char ch[20];
	int num(0);
	while(x || !num) ch[++num] = x % 10 + '0', x /= 10;
	while(num) putchar(ch[num--]);
	putchar('\n');
}
const int N = 2e4 + 79;
const int SIZ = 217;
int a[N], b[N];
int n, m;
int ans;
int block, tot;
int  L[SIZ], R[SIZ], belong[N], cnt[SIZ];
vector<int> s[SIZ];
struct BIT {
	int c[N];
	inline int lowbit(int x) {
		return x & -x;
	}
	inline void add(int x, int y) {
		for(; x <= n; x += lowbit(x)) c[x] += y;
	}
	inline int query(int x) {
		int ans(0);
		for(; x; x -= lowbit(x)) ans += c[x];
		return ans;
	}
} B;

inline void reset(int x) {
	s[x].clear();
	rep(i, L[x], R[x]) {
		s[x].push_back(a[i]);
		cnt[x]++;
	}
	sort(s[x].begin(),s[x].end());
}

inline void build() {

	rep(i, 1, tot) {
		L[i] = (i - 1) * block + 1;
		R[i] = i * block;
	}
	R[tot] = n;
	rep(i, 1, tot) reset(i);
}

#define ddd cout<<ans<<endl;

inline void change(int x, int y) {
	if(x > y) swap(x, y);
	if(belong[x] == belong[y]) {
		rep(i, x + 1, y) {
			if(a[i] < a[x])
			ans--;
			else ans++;

			if(a[i] > a[y])
				ans--;
			else ans++;
		}
	} else {
		rep(i, x + 1, R[belong[x]]) {
			if(a[i] < a[x])
			ans--;
			else ans++;

			if(a[i] > a[y])
				ans--;
			else ans++;
		}
		rep(i, L[belong[y]], y - 1) {
			if(a[i] < a[x])
			ans--;
			else ans++;

			if(a[i] > a[y])
				ans--;
			else ans++;
		}
		ddd
		rep(i, belong[x] + 1, belong[y] - 1) {
			ans-=lower_bound(s[i].begin(),s[i].end(),a[x])-s[i].begin();
//			cout<<lower_bound(s[i].begin(),s[i].end(),a[x])-s[i].begin()<<endl;
			
			ans+=s[i].size()-(upper_bound(s[i].begin(),s[i].end(),a[x])-s[i].begin());
				
			ans-=s[i].size()-(upper_bound(s[i].begin(),s[i].end(),a[y])-s[i].begin());
			
			ans+=lower_bound(s[i].begin(),s[i].end(),a[y])-s[i].begin();

		}
	}

	if(a[x] > a[y]) ans--;
	else ans++;
	swap(a[x], a[y]);
	reset(belong[x]);
	reset(belong[y]);
}


int main() {
		freopen("1.txt","r",stdin);

	read(n);

	block = sqrt(n);
	if(n % block) tot = block + 1;
	else tot = block;

	rep(i, 1, n) {
		read(a[i]);
		b[i] = a[i];
		belong[i] = (i - 1) / block + 1;
	}
	sort(b + 1, b + n + 1);
	int k = unique(b + 1, b + n + 1) - b - 1;
	rep(i, 1, n) {
		a[i] = lower_bound(b + 1, b + k + 1, a[i]) - b;
		ans += i - B.query(a[i] - 1) - 1; //¼õȥǰÃæ±ÈËüСµÄ
		B.add(i, 1);
	}
//	out(ans);
	build();
	read(m);
	int x, y;
	while(m--) {
		read(x);
		read(y);
		change(x, y);
//		out(ans);
	}
	return 0;
}

应该是change函数里面二分炸了。。但是不知道为什么