Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 20010

#define MAXB 150

int a[MAXN];

//block

int tot,L[MAXB],R[MAXB],belong[MAXN];

void build(int l,int r,int k)

{

	L[k] = l;R[k] = r;

	for(int i = l;i <= r;++i)belong[i] = k;

	return;

}

//discritise

int s[MAXN],b[MAXN],cnt = 0;

bool cmp(int x,int y){return a[x] < a[y];}

map<int,int> p;

struct BIT

{

	int c[MAXN];

	int lowbit(int x){return x&(-x);}

	void add(int p,int k){for(int i = p;i <= n;i += lowbit(i))c[i] += k;return;}

	int sum(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

}t[MAXB];

int ans = 0;

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	tot = sqrt(n);

	for(int i = 1;i <= tot;++i)build((i - 1) * tot + 1,i * tot,i);

	if(tot * tot < n){build(R[tot] + 1,n,tot + 1);++tot;}

	for(int i = 1;i <= n;++i)s[i] = i;

	sort(s + 1,s + 1 + n,cmp);

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

	{

		if(a[s[i]] == a[s[i - 1]])p[s[i]] = cnt;

		else p[s[i]] = ++cnt;

	}

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

	{

		t[belong[i]].add(p[i],1);

		for(int k = 1;k <= belong[i];++k)ans += t[k].sum(cnt) - t[k].sum(p[i]);

	}

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

	scanf("%d",&m);

	int x,y;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&x,&y);

		if(x > y)swap(x,y);

		if(belong[x] == belong[y])

		{

			for(int k = x + 1;k <= y - 1;++k)

			{

				if(a[k] > a[x])++ans;

				if(a[k] < a[x])--ans;

				if(a[k] > a[y])--ans;

				if(a[k] < a[y])++ans;

			}

		}

		else

		{

			for(int k = x + 1;k <= R[belong[x]];++k)

			{

				if(a[k] > a[x])++ans;

				if(a[k] < a[x])--ans;

				if(a[k] > a[y])--ans;

				if(a[k] < a[y])++ans;

			}

			for(int k = L[belong[y]];k <= y - 1;++k)

			{

				if(a[k] > a[x])++ans;

				if(a[k] < a[x])--ans;

				if(a[k] > a[y])--ans;

				if(a[k] < a[y])++ans;

			}

			for(int k = belong[x] + 1;k <= belong[y] - 1;++k)

			{

				ans += t[k].sum(cnt) - t[k].sum(p[x]);

				ans -= t[k].sum(p[x] - 1);

				ans -= t[k].sum(cnt) - t[k].sum(p[y]);

				ans += t[k].sum(p[y] - 1);

			}

		}

		if(a[x] > a[y])--ans;

		if(a[x] < a[y])++ans;

		t[belong[x]].add(p[x],-1);t[belong[y]].add(p[y],-1);

		t[belong[x]].add(p[y],1);t[belong[y]].add(p[x],1);

		swap(a[x],a[y]);swap(p[x],p[y]);

		cout << ans << endl;

	}

	return 0;

}