A sequence $A_1, A_2, \ldots, A_N$ of length $N$ is given. Write a program that processes the following queries:

• m k: Among subsequences of $A_1, A_2, \ldots, A_m$, the maximum length of a subsequence whose Longest Increasing Subsequence length does not exceed $k$. ($1 \le k \le m \le N$)

Input

The first line contains the length of the sequence $N$ and the number of queries $Q$. ($1 \le N \le 50{,}000$, $1 \le Q \le 200{,}000$)

The second line contains $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 50{,}000$)

The next $Q$ lines each contain a query in the format described above.

Output

For each query, output the answer on a separate line.

Examples

Sample Input 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

Sample Output 1

4
6
5
8
7
11