Sequence and Queries 44

Given a sequence $A_1, A_2, \ldots, A_N$ of length $N$, write a program that processes the following query.

• m k: Print the maximum length, among the subsequences of $A_1, A_2, \ldots, A_m$ whose longest increasing subsequence has length at most $k$. ($1 \le k \le m \le N$)

The first line contains $N$ and $Q$, the length of the sequence and the number of queries. ($1 \le N \le 50000$, $1 \le Q \le 200000$)

The second line contains $A_1, A_2, \ldots, A_N$. ($1 \le A_i \le 50000$)

Each of the next $Q$ lines contains a query as described above.

For each query, print the answer on its own line.