Камни

Перед Бобом выложены в ряд 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 запросов Алисы.

Входные данные

В первой строке входного файла INPUT.TXT заданы числа n и q – количество камней и запросов соответственно (2 ≤ n ≤ 10⁵; 1 ≤ q ≤ 10⁵).

Во второй строке заданы записанные на камнях целые числа a₁, a₂, ..., a_n (1 ≤ a_i ≤ n, все a_i различны).

В следующих q строках заданы запросы, j-й запрос задается парой целых чисел p_j и k_j (1 ≤ p_j ≤ n, 1 ≤ k_j ≤ n) – номером камня и номером шага, на котором этот камень должен быть покрашен в белый цвет.

Выходные данные

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

Примеры

Пояснение к примеру

В первом тестовом примере операции выполняются следующим образом:

• Если на первом шаге был выбран 1-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
• Если на первом шаге был выбран 2-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
• Если на первом шаге был выбран 3-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
• Если на первом шаге был выбран 4-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
• Если на первом шаге был выбран 5-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].
• Если на первом шаге был выбран 6-й камень: 1-й шаг: [1, 4, 6, 5, 2, 3], 2-й шаг: [1, 4, 6, 5, 2, 3], 3-й шаг: [1, 4, 6, 5, 2, 3], 4-й шаг: [1, 4, 6, 5, 2, 3], 5-й шаг: [1, 4, 6, 5, 2, 3], 6-й шаг: [1, 4, 6, 5, 2, 3].

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!