돌

보브 앞에 검은 돌 $n$개가 일렬로 놓여 있다. 돌에는 $1$부터 $n$까지 번호가 붙어 있다. $i$번째 돌에는 정수 $a_i$가 적혀 있다. $1$부터 $n$까지의 각 수는 정확히 한 돌에만 적혀 있으므로, $a_i$들은 순열을 이룬다. $i$번째 돌의 인접한 돌은 $(i-1)$번째 돌과 $(i+1)$번째 돌이다(존재하는 경우에 한한다).

보브는 다음 $n$단계를 수행한다.

• 1단계에서 보브는 $1$부터 $n$까지의 임의의 $i$를 고르고, $i$번째 돌을 흰색으로 칠한다.
• 2단계부터 $n$단계까지 보브는 흰 돌과 인접한 검은 돌들을 본다. 그중에서 $a_j$가 가장 작은 돌 $j$를 골라 흰색으로 칠한다.

모든 단계가 끝나면 돌 $n$개가 모두 흰색이 된다는 것은 쉽게 알 수 있다.

앨리스는 $q$개의 값 쌍 $p_j$, $k_j$를 골랐다. 각 쌍에 대해, 1단계에서 돌을 어떻게 고르면 $p_j$번째 돌이 정확히 $k_j$단계에 흰색이 되는지 알고 싶어 한다.

보브가 앨리스의 $q$개의 질의에 답하도록 도와라.

첫째 줄에 돌의 개수 $n$ ($2 \le n \le 10^5$)과 질의의 개수 $q$ ($1 \le q \le 10^5$)가 주어진다.

둘째 줄에 정수 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, 모든 $a_i$는 서로 다르다)이 주어진다.

다음 $q$개의 줄에 질의가 주어진다. $j$번째 질의는 두 정수 $p_j$와 $k_j$ ($1 \le p_j \le n$, $1 \le k_j \le n$)로 주어지며, 각각 돌의 번호와 그 돌이 흰색으로 칠해져야 하는 단계 번호이다.

각 질의에 대해, 1단계에 돌 $i$를 흰색으로 칠했을 때 $p_j$번째 돌이 $k_j$단계에 흰색이 되는 $i$의 개수를 출력한다. 답은 한 줄에 하나씩 출력한다.