Background

Translated from ROIR 2023 D2T3。

Problem Description

In front of Bob there are $n$ black stones arranged in a row, numbered from $1$ to $n$. On the $i$-th stone there is an integer $a_i$, and the integers on the $n$ stones form a permutation. We call the adjacent stones of the $i$-th stone the $(i-1)$-th and the $(i+1)$-th stones (if they exist).

Bob performs $n$ operations according to the following steps:

• In the first step, choose any $i$ ($1 \le i \le n$) and paint the $i$-th stone white.
• In steps $2$ to $n$, among all black stones that have at least one adjacent white stone, choose the stone $j$ with the smallest $a_i$ (that is, there may be many black stones whose adjacent stones include at least one white stone, but you must choose the one with the smallest $a_i$), and paint it white.

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

Alice chose $q$ pairs of values $p_j$ and $k_j$. For each pair $p$ and $k$, she wants to know how many different choices of the first step (i.e., which stone is painted white first) make the $p$-th stone become white at step $k$.

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.

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 one integer, representing the answer to the query.

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

1
2
1
2

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

0
1
1

Hint

In the explanation of the sample below, the bold numbers are the stones that are painted white.

In the first sample:

• If the first step chooses stone $1$:
  • 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 stone $2$:
  • 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 stone $3$:
  • 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 stone $4$:
  • 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 stone $5$:
  • 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 stone $6$:
  • 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 testdata.

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

Translated by ChatGPT 5