A new TV series about the life of programmers contains $n$ episodes, numbered from 1 to $n$. The Sirius TV company plans to air the episodes in order from the first to the last over $k$ days, showing a block of one or more consecutive episodes each day. Each episode will be shown exactly once.

Based on test screenings, the company's marketers have assigned a rating to each episode: the $i$-th episode is assigned a number $a_i$ from 1 to $n$, where the most interesting episode receives a rating of 1, and the most boring one receives a rating of $n$. The ratings of different episodes are distinct, so the numbers $[a_1, a_2, \dots, a_n]$ form a permutation.

Suppose a decision is made about which episodes will be shown on which day. For each day, we define the rating of that day as the rating of the most boring episode shown on that day. In other words, if episodes from $l_j$ to $r_j$ are shown on the $j$-th day, then the rating of that day $b_j$ is equal to the maximum value among $[a_{l_j}, a_{l_j+1}, \dots, a_{r_j}]$.

For the series broadcast to be successful, it is necessary to engage the viewers. Among all possible ways to divide the episodes into $k$ blocks over $k$ days, one must choose the one where the rating of the first day is as good as possible: $b_1$ is minimized. Among these ways, in turn, it is necessary to minimize the rating of the second day $b_2$, and given the chosen values of $b_1$ and $b_2$, minimize $b_3$, and so on. Thus, it is necessary to divide the broadcast of episodes into $k$ blocks in such a way as to lexicographically minimize the sequence $[b_1, b_2, \dots, b_k]$.

You need to answer $q$ queries, each of which is given by two numbers: $k$ and $i$. As an answer to the query, you must output the value $b_i$ — the rating of the $i$-th day for the optimal way to show the series in $k$ days.

Input

The first line of the input contains two integers $n$ and $q$ ($1 \leqslant n, q \leqslant 300\,000$) — the number of episodes and the number of queries, respectively.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leqslant a_i \leqslant n$) — the ratings of the episodes. It is guaranteed that the array $a$ is a permutation of integers from 1 to $n$.

The following $q$ lines each contain two integers $k$ and $i$ ($1 \leqslant i \leqslant k \leqslant n$) — the parameters of the query.

Output

Output the answer to each query in $q$ lines, in the order they are given in the input.

Examples

Input 1

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

Output 1

3
7
1
3

Input 2

3 1
2 3 1
2 2

Output 2

3

Note

Consider the first test:

• For $k = 7$, there is a unique way to show: show one episode each day. The ratings of the episodes by day are $[6], [4], [2], [3], [1], [7], [5]$, so $b = [6, 4, 2, 3, 1, 7, 5]$, and the answer to the query $k = 7$ and $i = 4$ is $b_4 = 3$.
• For $k = 1$, there is a unique way to show: show all episodes on the first day. The ratings of the episodes by day are $[6, 4, 2, 3, 1, 7, 5]$, so $b = [7]$, and the answer to the query $k = 1$ and $i = 1$ is $b_1 = 7$.
• For $k = 4$, it is optimal to show four episodes on the first day, and then one episode each for the next three days. The ratings of the episodes by day are $[6, 4, 2, 3], [1], [7], [5]$, so $b = [6, 1, 7, 5]$, and the answer to the query $k = 4$ and $i = 2$ is $b_2 = 1$.
• For $k = 5$, it is optimal to show two episodes on the first and last days, and one episode each on the remaining days. The ratings of the episodes by day are $[6, 4], [2], [3], [1], [7, 5]$, so $b = [6, 2, 3, 1, 7]$, and the answer to the query $k = 5$ and $i = 3$ is $b_3 = 3$.

Scoring