Longest Subsequence with Bounded Increasing Sequence

Consider a sequence \(B = (b_1, b_2, \ldots, b_n)\) of integers. A subsequence of a sequence \(A = (a_1, a_2, \ldots, a_k)\) is obtained by deleting some (possibly none or all) elements from \(A\) while preserving the order of the remaining elements. A subsequence is called increasing if its elements are strictly increasing. The longest increasing subsequence (LIS) of \(A\) is an increasing subsequence of maximum length. For example, the subsequences \((2,4,5,6)\) and \((1,4,5,6)\) are both longest increasing subsequences of \((2,1,1,4,7,5,6)\), each of length \(4\).

Now, given any subsequence \(C\) of \(B_m = (b_1, b_2, \ldots, b_m)\), if the length of the longest increasing subsequence of \(C\) is at most \(k\), we say that \(C\) is k-bounded.

Your task is: For a given sequence \(B\) and several queries, each query being two integers \(m\) and \(k\), determine the maximum possible length of a subsequence \(C\) (of \(B_m = (b_1, b_2, \ldots, b_m)\)) such that the longest increasing subsequence of \(C\) has length at most \(k\). Note that if \(B_m\) itself already has an LIS of length at most \(k\), then the whole sequence is admissible.

Input/Output Format: The input begins with two integers \(n\) and \(Q\) representing the length of \(B\) and the number of queries. The next line contains \(n\) integers representing the sequence \(B\). Each of the following \(Q\) lines contains two integers \(m\) and \(k\): for each query, you need to consider the sequence \(B_m = (b_1, b_2, \ldots, b_m)\) and output the maximum length of a subsequence whose longest increasing subsequence is at most \(k\).

inputFormat

The first line contains two integers \(n\) and \(Q\) -- the length of sequence \(B\) and the number of queries, respectively.

The second line contains \(n\) space-separated integers: \(b_1, b_2, \ldots, b_n\).

Each of the next \(Q\) lines contains two integers \(m\) and \(k\) representing a query. For each query, you will consider the prefix \(B_m = (b_1, b_2, \ldots, b_m)\) and determine the answer.

outputFormat

For each query, output a single integer on a new line representing the maximum length of a subsequence of \(B_m\) such that its longest increasing subsequence has length at most \(k\).

sample

7 2
2 1 1 4 7 5 6
7 4
7 3

7
5