問題
長さ$ \ 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 \ $を出力します。