Камни

Перед Бобом выложены в ряд $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$-м шаге.