题目描述

第一题要简单一点，数数应该够简单了吧，一一有n个数，他会依次数每个数，显然，数数的次数就是n个数的和，但一直数数太无聊了，一一有T次修改，每次修改会把n个数中的第x个数修改成y。现在你要求出初始数组的数数次数，以及每次修改后的数数次数。

输入格式

第一行一个数n，接下来一行n个数，第三行一个数T，接下来T行，每行两个数x和y。 




  




1<=n<=1000001<=T<=1000001<=x<=n1<=y<=1001<=初始数列中的每个数<=100 

输出格式

共T+1行，表示数数次数。

样例

输入

2
1 2
2

输出

1 2
2 3
3
4
5