由于 Grammy 日夜沉迷于《空洞骑士》而忘记了 Tony 布置的家庭作业，她已经没有时间完成了。作为 Grammy 的好朋友，你决定发挥你作为天才程序员的才能来帮助她。题目描述如下：

给定一个排列 $p = p_1, p_2, \dots, p_n$。我们定义 $A_i$ 为满足 $j < i \land p_j < p_i$ 的 $j$ 的个数，$B_i$ 为满足 $j > i \land p_j < p_i$ 的 $j$ 的个数，且 $C_i = \min(A_i, B_i)$。

共有 $m$ 次询问。对于第 $i$ 次询问，你需要输出交换 $p_u$ 和 $p_v$ 后 $\sum_{i=1}^n C_i$ 的值。注意，每次询问后我们都会将排列 $p$ 恢复原状，这意味着各次询问之间是相互独立的。

输入格式

输入包含单个测试用例。

第一行包含一个正整数 $n$ ($1 \le n \le 100\,000$)。保证 $p$ 是 $1, 2, \dots, n$ 的一个排列。

第二行包含 $n$ 个不同的整数 $p_1, p_2, \dots, p_n$ ($1 \le p_i \le n$)。

第三行包含一个正整数 $m$ ($1 \le m \le 200\,000$)。

接下来的 $m$ 行描述了 $m$ 次询问。第 $i$ 行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，表示第 $i$ 次询问的参数。注意 $u$ 可能等于 $v$。

输出格式

输出包含 $m$ 行。每行包含一个整数，表示第 $i$ 次询问的答案。

样例

样例输入 1

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

样例输出 1

7
6
6
7
7
6
8

样例输入 2

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

样例输出 2

3
0
0