Piggy recently learned about the Longest Increasing Subsequence (LIS). For an integer sequence $A = (a_1, a_2, \dots, a_k)$, a subsequence of $A$ is defined as: a sequence formed by deleting zero or more elements from $A$ (it is allowed to delete none, or all $k$ elements) and keeping the remaining elements in their original relative order. If the elements of this subsequence are strictly increasing from left to right, it is called an increasing subsequence of $A$. The increasing subsequence containing the maximum number of elements is called the Longest Increasing Subsequence of $A$. For example, $(2, 4, 5, 6)$ and $(1, 4, 5, 6)$ are both longest increasing subsequences of $(2, 1, 1, 4, 7, 5, 6)$, both with a length of 4.

Now, Piggy has encountered the following problem: given a sequence $B_m = (b_1, b_2, \dots, b_m)$, let $C$ be a subsequence of $B_m$ such that the length of the longest increasing subsequence of $C$ does not exceed $k$. What is the maximum possible length of $C$?

Piggy thinks this problem is too simple and lacks challenge, so he decided to propose a harder one. He gives you a sequence $B = (b_1, b_2, \dots, b_n)$ and several queries. Each query provides two integers $m$ and $k$. You need to answer the above problem for the sequence $B_m = (b_1, b_2, \dots, b_m)$ formed by the first $m$ elements of $B$ and the given $k$.

Input

The first line contains two integers $n$ and $q$, where $n$ is the length of sequence $B$ and $q$ is the number of queries.

The second line contains $n$ positive integers $b_1, b_2, \dots, b_n$ separated by spaces.

The next $q$ lines each contain two integers $m_i$ and $k_i$, representing a query for $m = m_i$ and $k = k_i$.

Output

Output $q$ lines, each containing one integer as the answer to the corresponding query in order.

Examples

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

Output 1

4
6
5
8
7
11

Input 2

See the files lis/lis2.in and lis/lis2.ans in the contestant directory.

Output 2

See the files lis/lis2.in and lis/lis2.ans in the contestant directory.

Note

Query 1: For the sequence $(9, 6, 3, 1, 5)$, we can choose the subsequence $(9, 6, 3, 1)$, whose longest increasing subsequence has length 1.

Query 2: For the sequence $(9, 6, 3, 1, 5, 12, 8)$, we can choose the subsequence $(9, 6, 3, 1, 12, 8)$, whose longest increasing subsequence has length 2.

Query 3: For the sequence $(9, 6, 3, 1, 5, 12, 8, 4, 2)$, we can choose the subsequence $(9, 6, 5, 4, 2)$, whose longest increasing subsequence has length 1.

Query 4: For the sequence $(9, 6, 3, 1, 5, 12, 8, 4, 2)$, we can choose the subsequence $(9, 6, 3, 1, 12, 8, 4, 2)$, whose longest increasing subsequence has length 2.

Query 5: For the sequence $(9, 6, 3, 1, 5, 12, 8, 4, 2, 2, 2)$, we can choose the subsequence $(9, 6, 5, 4, 2, 2, 2)$, whose longest increasing subsequence has length 1.

Query 6: For the sequence $(9, 6, 3, 1, 5, 12, 8, 4, 2, 2, 2)$, we can choose the subsequence $(9, 6, 3, 1, 5, 12, 8, 4, 2, 2, 2)$, whose longest increasing subsequence has length 3.

Constraints

For $100\%$ of the data, $1 \le n \le 50000$, $1 \le b_i \le 50000$, $1 \le q \le 200000$, $1 \le k_i \le m_i \le n$.