给定一个序列 $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$ 。
以下为子任务：（留空部分表示无特殊限制）
| 测试点编号 | $n$ | $q$ | $a_i,y$ | 特殊性质 | 时空限制 |
|---|---|---|---|---|---|
| 1-3 | $\le2000$ | $\le2000$ | A | 1s/500MB | |
| 4-5 | $=0$ | 1s/50MB | |||
| 6-10 | 3s/500MB | ||||
| 11-15 | 3s/500MB | ||||
| 16-20 | 1s/50MB |
特殊性质 A：保证数据完全随机