#include <cmath>

#include <cstdio>

#include <iostream>

#include <algorithm>

#define M 210

#define N 20101

using namespace std;

int n, m, t, S, C, ans;

int a[N], b[N], c[N], st[M], ed[M], belong[N], sorted[M][M], len[M];

inline int read()

{

	int x = 0, f = 1;

	char ch = getchar();

	for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';

	return x * f;

}

inline int query(int x)

{

	int ret = 0;

	for(; x; x -= x & -x) ret += c[x];

	return ret;

}

inline void add(int x)

{

	for(; x <= m; x += x & -x) c[x]++;

}

inline void init()

{

	int i, j;

	S = sqrt(n);

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

	{

		st[++C] = i;

		ed[C] = min(i + S - 1, n);

		len[C] = ed[C] - st[C] + 1;

	}

	for(i = 1; i <= C; i++)

	{

		for(j = st[i]; j <= ed[i]; j++)

			belong[j] = i, sorted[i][j - st[i] + 1] = a[j];

		sort(sorted[i] + 1, sorted[i] + len[i] + 1);

	}

}

inline void solve(int x, int y)

{

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

	int i, l = belong[x], r = belong[y], tmp;

	if(l == r)

		for(i = x + 1; i < y; i++)

		{

			ans -= (a[i] < a[x]);

			ans += (a[i] > a[x]);

			ans -= (a[i] > a[y]);

			ans += (a[i] < a[y]);

		}

	else

	{

		for(i = l + 1; i < r; i++)

		{

			ans -= lower_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[x]) - sorted[i] - 1;

			ans += len[i] - (upper_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[x]) - sorted[i]) + 1;

			ans -= len[i] - (upper_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[y]) - sorted[i]) + 1;

			ans += lower_bound(sorted[i] + 1, sorted[i] + len[i] + 1, a[y]) - sorted[i] - 1;

		}

		for(i = x + 1; i <= ed[l]; i++)

		{

			ans -= (a[i] < a[x]);

			ans += (a[i] > a[x]);

			ans -= (a[i] > a[y]);

			ans += (a[i] < a[y]);

		}

		for(i = st[r]; i < y; i++)

		{

			ans -= (a[i] < a[x]);

			ans += (a[i] > a[x]);

			ans -= (a[i] > a[y]);

			ans += (a[i] < a[y]);

		}

	}

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

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

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

	for(i = st[l]; i <= ed[l]; i++) sorted[l][i - st[l] + 1] = a[i];

	for(i = st[r]; i <= ed[r]; i++) sorted[r][i - st[r] + 1] = a[i];

	sort(sorted[l] + 1, sorted[l] + len[l] + 1);

	sort(sorted[r] + 1, sorted[r] + len[r] + 1);

}

int main()

{

	int i, x, y;

	n = read();

	for(i = 1; i <= n; i++) a[i] = b[i] = read();

	sort(b + 1, b + n + 1);

	m = unique(b + 1, b + n + 1) - b - 1;

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

	{

		a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;

		ans += i - query(a[i]) - 1, add(a[i]);

	}

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

	init();

	t = read();

	while(t--)

	{

		x = read();

		y = read();

		solve(x, y);

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

	}

	return 0;

}