長さ $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$)
2 行目には $A_1, A_2, \ldots, A_N$ が与えられる。($1 \le A_i \le 50{,}000$)
続く $Q$ 行には、それぞれ上記の形式のクエリが 1 行ずつ与えられる。
出力
各クエリに対する答えを別の行に出力せよ。
入出力例
入力例 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