P10100 [ROIR 2023] Stones (Day 2)

Translated from [ROIR 2023 D2T3](https://neerc.ifmo.ru/school/archive/2022-2023/ru-olymp-regional-2023-day2.pdf)。

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.

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$.

For each query, output one integer, representing the answer to the query.

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. | Subtask ID | Points | Special Property | | :----------: | :----------: | :----------: | | $1$ | $20$ | $n, q \le 300$ | | $2$ | $17$ | $n \le 3000$ | | $3$ | $12$ | $n \le 50000, q \le 10$ | | $4$ | $6$ | The values of $a_i$ are increasing | | $5$ | $16$ | All $k_i$ are equal | | $6$ | $15$ | All $p_i$ are equal | | $7$ | $14$ | No special property | 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