002 - Increasing Sequence 2

問題

長さ$ \ N \ $の数列$ \ A \ (a_1,a_2,\ldots,a_N) \ $が与えられます。

$Q \ $個のクエリが与えられます。$i \ (1 \leq i \leq Q) \ $番目のクエリでは整数$ \ x_i,v_i \ $が与えられ、クエリの内容は以下の通りです。

• $a_{x_i} \ $に$ \ v_i \ $を加算する

ここで、$i \ $番目までのクエリを処理した時点での数列$ \ A \ $を$ \ A_i \ $とします。
$A_1,A_2,\ldots,A_Q \ $のうち広義単調増加なものの個数を求めてください。

なお、数列$ \ B \ (b_1,b_2,\ldots,b_m) \ $が$ \ b_1 \leq b_2 \leq \ldots \leq b_m \ $を満たすとき数列$ \ B \ $は広義単調増加であるといいます。

入力

入力は以下の形式で標準入力から与えられる。

$N \ Q$
$a_1 \ a_2 \ \ldots \ a_N$
$x_1 \ v_1$
$x_2 \ v_2$
$\vdots$
$x_Q \ v_Q$

出力

$A_1,A_2,\ldots,A_Q \ $のうち広義単調増加なものの個数を出力せよ。

制約

全ての入出力ケースについて以下を満たす。

• $2 \leq N \leq 3 \times 10^5$
• $1 \leq Q \leq 3 \times 10^5$
• $1 \leq a_i \leq 10^9$
• $1 \leq x_i \leq N$
• $1 \leq v_i \leq 10^9$

入出力例

入力例

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

出力例

2

• $A_1 = (1,3,4,5,6)$
• $A_2 = (1,3,4,9,6)$
• $A_3 = (1,3,4,9,12)$

条件を満たすのは$ \ A_1 \ $と$ \ A_3 \ $の$ \ 2 \ $つなので$ \ 2 \ $を出力します。