길이가 $N$인 수열 $A_1, A_2, \ldots, A_N$이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• m k: $A_1, A_2, \ldots, A_m$ 의 부분수열 (subsequence) 중 최장 증가 부분수열의 길이가 $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$개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다.

출력

각 쿼리에 대해 정답을 한 줄에 출력하라.

Sample

Input

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

Output

4
6
5
8
7
11