给定一个序列 $a$ ，我们定义一个二元组 $(i,j)$ 为一个逆序对当且仅当 $i< j$ 且 $a_i>a_j$ 。定义两个逆序对 $(i_1,j_1),(i_2,j_2)$ 本质不同 当且仅当 $a_{i_1}\ne a_{i_2}$ 或 $a_{j_1}\ne a_{j_2}$ 。

现在给出 $a$ 序列，问本质不同逆序对个数。

这还不够。

现在有 $q$ 组修改，每一次修改形如 $x~y$ 表示修改 $a_x$ 为 $y$ ，每一次修改 不互相独立 ，即这一次修改会影响到后面的所有修改。

你需要对于每一次修改输出序列本质不同逆序对个数。

为了体现本题的不同解法，本题不同测试点拥有不同的时空限制。

输入格式

第一行一个整数 $n$ ，表示序列长度。

第二行 $n$ 个整数 $a_i$ ，表示序列 $a$ 。

第三行一个整数 $q$ ，表示询问组数。

后面 $q$ 行每行两个整数表示一次修改。

输出格式

一行一个整数，表示初始序列中本质不同逆序对个数。

后面 $q$ 行每行一个整数，第 $i + 1$ 行表示第 $i$ 次修改后序列本质不同逆序对个数。

样例数据

样例 1 输入

5
3 1 2 1 5 
1
3 3

样例 1 输出

3
1

样例 2 输入

6
1 1 4 5 1 4
3
1 5
1 1
4 4

样例 2 输出

3
3
3
1

样例 3 输入

15
6 14 12 12 6 8 9 3 8 14 14 15 6 15 2 
10
12 13
10 10
14 9
8 8
11 11
5 8
1 6
11 12
2 13
1 9

样例 3 输出

23
25
29
30
24
29
29
29
24
20
20

子任务

Idea：DPair，Solution：DPair，Code：DPair，Data：DPair

对于 $100\%$ 的数据 $1\le n,q \le 10^5, 1\le a_i, x, y, \le n$ 。

以下为子任务：（留空部分表示无特殊限制）

特殊性质 A：保证数据完全随机