AT_abc393_f [ABC393F] Prefix LIS Query

長さ $ N $ の整数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。 $ Q $ 個のクエリを処理してください。 $ i\ (1\leq i\leq Q) $ 番目のクエリは以下の通りです： - 整数 $ R_i,X_i $ が与えられる。数列 $ (A_1,A_2,\dots,A_{R_i}) $ の（連続とは限らない）部分列であって、狭義単調増加であり、かつ全ての要素が $ X_i $ 以下であるようなものの長さの最大値を求めよ。 なお、 $ X_i \geq \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace $ が保証される。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ R_1 $ $ X_1 $ $ R_2 $ $ X_2 $ $ \vdots $ $ R_Q $ $ X_Q $

$ Q $ 行出力せよ。 $ i\ (1\leq i \leq Q) $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 - $ 1 $ 番目のクエリ：数列 $ (2,4) $ の狭義単調増加な部分列であって、全ての要素が $ 5 $ 以下であるようなものの長さの最大値は $ 2 $ です。 具体的には、部分列 $ (2,4) $ が該当します。 - $ 2 $ 番目のクエリ：数列 $ (2,4,1,3,3) $ の狭義単調増加な部分列であって、全ての要素が $ 2 $ 以下であるようなものの長さの最大値は $ 1 $ です。 具体的には、部分列 $ (2) $ および $ (1) $ が該当します。 - $ 3 $ 番目のクエリ：数列 $ (2,4,1,3,3) $ の狭義単調増加な部分列であって、全ての要素が $ 3 $ 以下であるようなものの長さの最大値は $ 2 $ です。 具体的には、部分列 $ (2,3) $ および $ (1,3) $ が該当します。 ### Constraints - $ 1\leq N,Q \leq 2\times 10^5 $ - $ 1\leq A_i \leq 10^9 $ - $ 1\leq R_i\leq N $ - $ \min\lbrace A_1, A_2,\dots,A_{R_i} \rbrace\leq X_i\leq 10^9 $ - 入力は全て整数