AT_abc393_f [ABC393F] Prefix LIS Query

[problemUrl]: https://atcoder.jp/contests/abc393/tasks/abc393_f 给定一个长度为 $ 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\{ A_1, A_2, \dots, A_{R_i} \} $。

输入通过标准输入给出，格式如下： > $ 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 $ 个查询的答案。

### 约束条件 - $ 1 \leq N, Q \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - $ 1 \leq R_i \leq N $ - $ \min\{ A_1, A_2, \dots, A_{R_i} \} \leq X_i \leq 10^9 $ - 输入中所有值均为整数 ### 样例解释 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) $ 满足条件。 翻译由 DeepSeek R1 完成