Stones

Bob has $n$ black stones laid out in a row, numbered from $1$ to $n$. Stone $i$ has an integer $a_i$ written on it. Each number from $1$ to $n$ is written on exactly one stone, so the values $a_i$ form a permutation. The neighbors of stone $i$ are stones $i-1$ and $i+1$, if they exist.

Bob performs the following $n$ steps:

• In step 1, Bob picks any $i$ from $1$ to $n$ and paints stone $i$ white.
• In steps 2 through $n$, Bob looks at the black stones that neighbor at least one white stone. He picks the stone $j$ among them with the smallest $a_j$ and paints it white.

It is easy to see that after all steps, all $n$ stones are white.

Alice has chosen $q$ pairs of values $p_j$ and $k_j$. For each pair, she wants to know how many choices of the stone in step 1 make stone $p_j$ turn white exactly at step $k_j$.

Help Bob answer Alice's $q$ queries.

The first line contains two integers $n$ ($2 \le n \le 10^5$), the number of stones, and $q$ ($1 \le q \le 10^5$), the number of queries.

The second line contains the integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$, all $a_i$ are distinct).

Each of the next $q$ lines contains a query, given as two integers $p_j$ and $k_j$ ($1 \le p_j \le n$, $1 \le k_j \le n$): the number of a stone and the step at which that stone must be painted white.

For each query, print the number of values $i$ such that if stone $i$ is painted white in step 1, then stone $p_j$ is painted white in step $k_j$. Print one answer per line.