#P17890. JamBrains

JamBrains

一份文件有 nn 行,第 ii 行有 sis_i 个光标位置,记为 (i,1),…,(i,si)(i,1),\ldots,(i,s_i)。可以使用两个按键:

  • Up:在 (i,j)(i,j) 时,若 i=1i=1 则不动;否则移动到 (i−1,min⁡(j,si−1))(i-1,\min(j,s_{i-1}))。
  • Right:若 j<sij<s_i,移动到 (i,j+1)(i,j+1);否则移动到下一行的 (i+1,1)(i+1,1)。在整个文件最后一个位置 (n,sn)(n,s_n) 时不动。

从某个位置出发,反复执行“按 uu 次 Up,再按 rr 次 Right”。若在某次按键后光标到达第一行,则这个起始位置称为成功位置;第一行的起始位置本身也算成功。

求成功位置的数量。还要依次处理 qq 次修改,每次将 sposs_{\mathrm{pos}} 改为 xx。请输出初始答案及每次修改后的答案。

输入格式

第一行三个整数 n,u,rn,u,r,1≤n≤1051\le n\le10^5,1≤u,r≤10181\le u,r\le10^{18}。

第二行 nn 个整数 sis_i,1≤si≤10121\le s_i\le10^{12}。

第三行整数 qq,1≤q≤1051\le q\le10^5。

接着 qq 行,每行两个整数 pos,x\mathrm{pos},x,1≤pos≤n1\le\mathrm{pos}\le n,1≤x≤10121\le x\le10^{12}。

修改作用于当前文件状态。

输出格式

输出 q+1q+1 行,每行一个整数,依次为修改前及每次修改后的成功位置数。

样例

5 2 5
5 2 4 3 1
1
1 1
15
11
5 2 10
5 2 4 3 1
1
2 3
11
12
10 1 42
169 42 42 42 42 42 42 42 42 42
1
2 43
211
254

第一组初始状态从 (5,1)(5,1) 出发,若干轮后会在 Up 阶段到达第一行,所以它是成功位置。判断成功时需要考虑一轮内部经过的位置。