Перед Бобом выложены в ряд n черных камней, пронумерованных от 1 до n. На i-м камне записано целое число ai.
Для каждого числа от 1 до n известно, что оно записано ровно на одном
камне, иными словами числа ai образуют перестановку. Будем называть соседними для i-го камня (i−1)-й и (i+1)-й камни (если они существуют).
Боб выполняет следующие n шагов:
На первом шаге Боб выбирает произвольное i от 1 до n и красит i-й камень в белый цвет.
На шагах с номерами от 2 до n Боб смотрит на такие черные камни, которые являются соседними для хотя бы одного белого камня, из них он выбирает камень j с минимальным aj и красит его в белый цвет.
Несложно заметить, что к концу выполнения всех шагов перед Бобом будут лежать n белых камней.
Алиса выбрала q пар значений pj и kj. Для каждой пары она хочет выяснить, сколько существует различных способов выбрать камень на первом шаге, которые приведут к тому, что камень с номером pj станет белым ровно на kj-м шаге.
Помогите Бобу ответить на q запросов Алисы.
Входные данные
На первой строке заданы числа n — количество камней (2≤n≤105) и q — количество запросов (1≤q≤105).
На второй строке заданы записанные на камнях целые числа a1,a2,…,an (1≤ai≤n, все ai различны).
На следующих q строках заданы запросы, j-й запрос задается парой целых чисел pj и kj
(1≤pj≤n, 1≤kj≤n) — номером камня и номером шага, на котором этот камень должен
быть покрашен в белый цвет.
Выходные данные
Для каждого запроса выведите количество значений i, таких что если i-й камень будет покрашен в белый цвет на первом шаге, то pj-й камень покрасится в белый цвет на kj-м шаге.
Подзадачи
№
баллы
необх. подзадачи
ограничения
1
20
-
n≤300,q≤300
2
17
1
n≤3000
3
12
-
n≤50000,q≤10
4
6
-
значения ai возрастают
5
16
-
все значения ki одинаковые
6
15
-
все значения pi одинаковые
7
14
1, 2, 3, 4, 5, 6
Нет доп. ограничений
STDIN
STDOUT
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
Примечание
В первом тестовом примере операции выполняются следующим образом:
Если на первом шаге был выбран 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].