分数: 500 点
问题陈述
给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 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.
约束
- 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
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q A_1 A_2 \dots A_N R_1 X_1 R_2 X_2 \vdots R_Q X_Q
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i-第一个查询。
示例输入 1
5 3 2 4 1 3 3 2 5 5 2 5 3
示例输出 1
2 1 2
- 第一个查询:对于序列 (2,4),最多包含所有元素的最长严格递增子序列 5 有长度 2.
具体来说, (2,4) 符合资格。 - 第二个查询:对于序列 (2,4,1,3,3),最多包含所有元素的最长严格递增子序列 2 有长度 1.
具体来说, (2) 和 (1) 符合资格。 - 第三个查询:对于序列 (2,4,1,3,3),最多包含所有元素的最长严格递增子序列 3 有长度 2.
具体来说, (2,3) 和 (1,3) 符合资格。
示例输入 2
10 8 2 5 6 5 2 1 7 9 7 2 7 8 5 2 2 3 2 6 7 3 8 9 9 6 8 7
示例输出 2
4 1 1 2 1 5 3 4