长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$ 给定。此时，编写一个程序执行以下查询：
m k: 在 $A_1, A_2, \ldots, A_m$ 的子序列中，最长递增子序列 的长度不超过 $k$ 的子序列的最大长度。($1 \le k \le m \le N$)
输入格式
第一行包含序列的大小 $N$ 和查询的数量 $Q$。($1 \le N \le 50{,}000$, $1 \le Q \le 200{,}000$)
第二行包含 $A_1, A_2, \ldots, A_N$。($1 \le A_i \le 50{,}000$)
接下来 $Q$ 行，每行包含一个上述格式的查询。
输出格式
对于每个查询，在一行中输出答案。
样例
样例输入 1
11 6 9 6 3 1 5 12 8 4 2 2 2 5 1 7 2 9 1 9 2 11 1 11 11
样例输出 1
4 6 5 8 7 11