Problem Description

Bob is facing a row of $n$ black stones, numbered from $1$ to $n$. The $i$-th stone has an integer $a_i$ written on it, and the integers on the $n$ stones form a permutation. The adjacent stones of the $i$-th stone are the $(i-1)$-th and $(i+1)$-th stones, if they exist.

Bob performs $n$ operations as follows:

• In the first step, he chooses any $i$ ($1 \le i \le n$) and paints the $i$-th stone white.
• From the second to the $n$-th step, he selects the black stone $j$ with the smallest $a_i$ among those whose adjacent stones include at least one white stone, and paints it white.

It is clear that after all steps are completed, all $n$ stones will be white.

Alice has chosen $q$ pairs of values $p_j$ and $k_j$. For each pair of $p$ and $k$, she wants to know how many different ways there are to choose which stone to paint white in the first step, such that the $p$-th stone becomes white in the $k$-th step.

Help Bob answer Alice's $q$ queries.

Input Format

The first line contains two integers $n$ and $q$, representing the number of stones and the number of queries, respectively.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$, representing the integers written on the stones.

The next $q$ lines each contain a pair of integers $p_j$ and $k_j$.

Output Format

For each query, output a single integer representing the answer to the query.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1
2
1
2

Sample Input #2

5 3
5 2 3 4 1
2 3
4 4
3 2

Sample Output #2

0
1
1

Notes/Hints

The bold numbers in the sample explanations indicate the stones that are painted white.

In the first sample:

• If the first step chooses the 1st stone:
• Step 1: $[\bold1, \gray4, \gray6, \gray5, \gray2, \gray3]$;
• Step 2: $[\bold1, \bold4, \gray6, \gray5, \gray2, \gray3]$;
• Step 3: $[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$;
• Step 4: $[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$;
• Step 5: $[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$;
• Step 6: $[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$.
• If the first step chooses the 2nd stone:
• Step 1: $[\gray1, \bold4, \gray6, \gray5, \gray2, \gray3]$;
• Step 2: $[\bold1, \bold4, \gray6, \gray5, \gray2, \gray3]$;
• Step 3: $[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$;
• Step 4: $[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$;
• Step 5: $[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$;
• Step 6: $[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$.
• If the first step chooses the 3rd stone:
• Step 1: $[\gray1, \gray4, \bold6, \gray5, \gray2, \gray3]$;
• Step 2: $[\gray1, \bold4, \bold6, \gray5, \gray2, \gray3]$;
• Step 3: $[\bold1, \bold4, \bold6, \gray5, \gray2, \gray3]$;
• Step 4: $[\bold1, \bold4, \bold6, \bold5, \gray2, \gray3]$;
• Step 5: $[\bold1, \bold4, \bold6, \bold5, \bold2, \gray3]$;
• Step 6: $[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$.
• If the first step chooses the 4th stone:
• Step 1: $[\gray1, \gray4, \gray6, \bold5, \gray2, \gray3]$;
• Step 2: $[\gray1, \gray4, \gray6, \bold5, \bold2, \gray3]$;
• Step 3: $[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$;
• Step 4: $[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$;
• Step 5: $[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$;
• Step 6: $[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$.
• If the first step chooses the 5th stone:
• Step 1: $[\gray1, \gray4, \gray6, \gray5, \bold2, \gray3]$;
• Step 2: $[\gray1, \gray4, \gray6, \gray5, \bold2, \bold3]$;
• Step 3: $[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$;
• Step 4: $[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$;
• Step 5: $[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$;
• Step 6: $[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$.
• If the first step chooses the 6th stone:
• Step 1: $[\gray1, \gray4, \gray6, \gray5, \gray2, \bold3]$;
• Step 2: $[\gray1, \gray4, \gray6, \gray5, \bold2, \bold3]$;
• Step 3: $[\gray1, \gray4, \gray6, \bold5, \bold2, \bold3]$;
• Step 4: $[\gray1, \gray4, \bold6, \bold5, \bold2, \bold3]$;
• Step 5: $[\gray1, \bold4, \bold6, \bold5, \bold2, \bold3]$;
• Step 6: $[\bold1, \bold4, \bold6, \bold5, \bold2, \bold3]$.

This problem uses bundled test cases.

For 100% of the data, $2 \le n \le 10^5$, $1 \le q \le 10^5$, $1 \le a_i \le n$ with all $a_i$ distinct, and $1 \le p_j, k_j \le n$.

见题面 Input 部分

见题面 Output 部分