绝地武士团的大师尤达（Yoda）想出了一个在幼徒中举办锦标赛的主意。他还没有确定日期，但已经决定了锦标赛的赛制。

绝地圣殿里有 $N$ 名幼徒。尤达可以感知到幼徒体内的原力，并且他可以将第 $i$ 名幼徒体内的原力值表示为一个数字 $f_i$。

因此，锦标赛的赛制如下：首先，尤达让孩子们按照 $f_i$ 非递增的顺序排成一排。然后，队列中的第一名幼徒与其余所有幼徒联合起来进行对抗。这场战斗基于光剑对决，非常壮观。然而，尤达知道结果只取决于竞争者体内的原力。如果一名幼徒的原力值不小于他所有对手的原力总和，那么他就会获胜。在这种情况下，他被视为获胜者之一。否则，他就会失败。无论如何，在那之后他都会从队列中被移除，锦标赛继续进行。同样，最强（队列中的第一位）的幼徒以相同的赛制与队列中剩余的所有人对抗，如果他获胜，他也被视为获胜者之一。之后他被移除，锦标赛以相同的赛制继续进行，直到队列中只剩下一名孩子。他会自动成为获胜者之一，锦标赛结束。

尤达想知道获胜者的总数。然而，由于锦标赛一再推迟，幼徒体内的原力值会不时发生变化。请帮助尤达计算每次变化后获胜者的总数。

输入格式

输入的第一行包含一个整数 $N$，表示绝地圣殿中幼徒的数量（$1 \le N \le 100\,000$）。

第二行包含 $N$ 个整数 $f_1, f_2, \dots, f_N$，表示幼徒体内的原力值（$1 \le f_i \le 10^{12}$）。

第三行包含一个整数 $M$，表示幼徒原力值的变化次数（$0 \le M \le 50\,000$）。

接下来的 $M$ 行包含有关变化的信息。其中第 $i$ 行描述第 $i$ 次变化，包含两个整数 $k$ 和 $f_k^*$，表示第 $k$ 名幼徒体内的原力值变为 $f_k^*$（$1 \le k \le N, 1 \le f_k^* \le 10^{12}$）。

输出格式

输出 $M + 1$ 行，每行包含一个整数。

第一行输出在没有任何变化之前锦标赛的获胜者人数。

对于所有 $i > 0$，第 $(i + 1)$ 行输出在前 $i$ 次变化之后锦标赛的获胜者人数。

样例

样例输入 1

3
2 1 3
3
1 3
2 7
3 5

样例输出 1

3
2
3
2

样例输入 2

7
2 14 14 15 5 2 5
5
5 2
4 12
5 4
3 10
7 9

样例输出 2

4
3
3
3
3
4