题目背景

距今 300 年前，史前科学文明跨越了界限。出现了凌驾人类的人工智能，也就是超人机械。

不为人知的诞生，等察觉到时，世界已经在【他】的手中了。

究竟他身在何处，有什么样的外貌，虽然直到最后都没有人知道。但他好像可以出现在任何地方，化为任何样貌。

既非敌对，也非压制，单纯只是力量上占上风而已。也不太常出手进行干涉。我想一定是人类对他来说无所谓吧。

但即使如此，他还是会帮人实现愿望，魔人或魔龙，各式各样的不可思议，都是有人追求才被造出来的。

......

然而在某一天，超人机械消失了。

被腐铁菌干掉了，只是躲了起来，启程前往次元的另一端等，众说纷纭。留下的只有超人机械莫名其妙的发明品。和被世人自己弄得一团乱的世界。

这座树海一定也是超人机械的产物。魔力会一下子增幅，一下子又消耗掉对吧？魔法是从异次元将力量取出的能力，是超出人类理解范围的技术。

题目描述

给定一个序列 $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$ 次修改后序列本质不同逆序对个数。

5
3 1 2 1 5 
1
3 3

3
1

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

3
3
3
1

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

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$			A	1s/500MB	Sample1
4-5		$=0$			1s/50MB	Sample2
6-10					3s/500MB	Sample3
11-15
16-20					1s/50MB

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