28414번 - Камни 서브태스크다국어

Перед Бобом выложены в ряд $n$ черных камней, пронумерованных от $1$ до $n$. На $i$-м камне записано целое число $a_i$. Для каждого числа от $1$ до $n$ известно, что оно записано ровно на одном камне, иными словами числа $a_i$ образуют перестановку. Будем называть соседними для $i$-го камня $(i - 1)$-й и $(i + 1)$-й камни (если они существуют).

Боб выполняет следующие $n$ шагов:

• На первом шаге Боб выбирает произвольное $i$ от $1$ до $n$ и красит $i$-й камень в белый цвет.
• На шагах с номерами от $2$ до $n$ Боб смотрит на такие черные камни, которые являются соседними для хотя бы одного белого камня, из них он выбирает камень $j$ с минимальным $a_j$ и красит его в белый цвет.

Несложно заметить, что к концу выполнения всех шагов перед Бобом будут лежать $n$ белых камней.

Алиса выбрала $q$ пар значений $p_j$ и $k_j$. Для каждой пары она хочет выяснить, сколько существует различных способов выбрать камень на первом шаге, которые приведут к тому, что камень с номером $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$) — номером камня и номером шага, на котором этот камень должен быть покрашен в белый цвет.

Для каждого запроса выведите количество значений $i$, таких что если $i$-й камень будет покрашен в белый цвет на первом шаге, то $p_j$-й камень покрасится в белый цвет на $k_j$-м шаге.