3885: 罗dalao的方案

xiyue大佬发明了一个游戏，于是他邀请罗dalao来玩。
首先，xiyue大佬摆出n只怪兽，编号为1到n，编号为i的能力值为a_i。
罗dalao要想打过某只怪兽，他的能力值一定要大于等于这只怪兽，游戏规定他必须从编号1的怪兽顺序打到编号为n的，同时规定他的初始能力值为0，所以他需要氪金。
(当他打到某个怪兽时自己能力值不够了，就该氪一次金了，罗dalao每次氪金都氪到自己的能力值刚刚够打当前怪兽)
罗dalao想减少氪金的次数，他想偷偷做手脚而不被发现，将编号为x的怪兽能力值改成y，从而减少氪金次数
于是他偷偷搞到了所有怪兽的能力值，并给出做手脚的方案，请你告诉他对于每个方案，需要氪多少次金，不然他就要不停的氪金了

单组数据
第一行一个整数n表示怪兽个数(1<=n<=200000)
第二行n个整数，第i个为a_i，表示编号为i的怪兽的能力值(1<=a_i<=1000000000)
第三行一个整数m，表示罗dalao将给出m种方案(1<=m<=100000)
接下来m行，每行两个用空格隔开的整数x y，表示将编号为x的怪兽能力值改为y(1<=x<=n，1<=y<=1000000000)

对于每种方案，输出一行一个整数代表答案

5
1 2 3 4 5
3
3 7
1 9
4 2

3
1
4