409691: GYM103687 F Easy Fix

Since Grammy plays Hollow Knight day and night and forgets the homework Tony gives her, she already has no time to do it. As a talented programmer and good friend of Grammy, you decide to help her. The problem is described as follows.

Given a permutation $$$p = p_1, p_2, \dots, p_n$$$. We define $$$A_i$$$ as the number of $$$j$$$ satisfying that $$$j<i\land p_j<p_i$$$, $$$B_i$$$ as the number of $$$j$$$ satisfying that $$$j>i\land p_j<p_i$$$, and $$$C_i=\min(A_i,B_i)$$$.

There are $$$m$$$ queries. For the $$$i$$$-th query, you should output the value of $$$\sum_{i=1}^n C_i$$$ if we swap $$$p_u$$$ and $$$p_v$$$. Note that we will recover the permutation $$$p$$$ after each query which means queries are independent of each other.

The input contains only a single case.

The first line contains one positive integer $$$n$$$ ($$$1\leq n\leq 100\,000$$$). It is guaranteed that $$$p$$$ is a permutation of $$$1,2,\dots,n$$$.

The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \dots, p_n$$$ ($$$1\leq p_i\leq n$$$).

The third line contains one positive integer $$$m$$$ ($$$1\leq m\leq 200\,000$$$).

The following $$$m$$$ lines describe $$$m$$$ queries. The $$$i$$$-th line contains two integers $$$u$$$ and $$$v$$$ ($$$1\leq u,v\leq n$$$), denoting the parameter of the $$$i$$$-th query. Note that $$$u$$$ may be equal to $$$v$$$.

The output contains $$$m$$$ lines. Each line contains one integer, denoting the answer to the $$$i$$$-th query.

7
1 6 2 7 5 4 3
7
1 7
2 6
3 5
4 4
1 1
2 1
3 7

7
6
6
7
7
6
8

5
5 3 1 2 4
3
3 1
2 5
3 3

3
0
0