Задача №115212. Камни
Перед Бобом выложены в ряд \(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, \ldots, a_n\) (\(1 \le a_i \le n\), все \(a_i\) различны).
На следующих \(q\) строках заданы запросы, \(j\)-й запрос задается парой целых чисел \(p_j\) и \(k_j\) (\(1 \leq p_j \leq n\), \(1 \leq k_j \leq n\)) — номером камня и номером шага, на котором этот камень должен быть покрашен в белый цвет.
Для каждого запроса выведите количество значений \(i\), таких что если \(i\)-й камень будет покрашен в белый цвет на первом шаге, то \(p_j\)-й камень покрасится в белый цвет на \(k_j\)-м шаге.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 20 | \(n \le 300, q \le 300\) | первая ошибка | |
| 2 | 17 | \(n \le 3000\) | 1 | первая ошибка |
| 3 | 12 | \(n \le 50000, q \le 10\) | первая ошибка | |
| 4 | 6 | значения \(a_i\) возрастают | первая ошибка | |
| 5 | 16 | все значения \(k_i\) одинаковые | первая ошибка | |
| 6 | 15 | все значения \(p_i\) одинаковые | первая ошибка | |
| 7 | 14 | нет | 1–6 | первая ошибка |
В первом тестовом примере операции выполняются следующим образом:
-
Если на первом шаге был выбран \(1\)-й камень: \(1\)-й шаг: \([\textbf{1}, 4, 6, 5, 2, 3]\), \(2\)-й шаг: \([\textbf{1, 4}, 6, 5, 2, 3]\), \(3\)-й шаг: \([\textbf{1, 4, 6}, 5, 2, 3]\), \(4\)-й шаг: \([\textbf{1, 4, 6, 5}, 2, 3]\), \(5\)-й шаг: \([\textbf{1, 4, 6, 5, 2}, 3]\), \(6\)-й шаг: \([\textbf{1, 4, 6, 5, 2, 3}]\).
-
Если на первом шаге был выбран \(2\)-й камень: \(1\)-й шаг: \([1, \textbf{4}, 6, 5, 2, 3]\), \(2\)-й шаг: \([\textbf{1, 4}, 6, 5, 2, 3]\), \(3\)-й шаг: \([\textbf{1, 4, 6}, 5, 2, 3]\), \(4\)-й шаг: \([\textbf{1, 4, 6, 5}, 2, 3]\), \(5\)-й шаг: \([\textbf{1, 4, 6, 5, 2}, 3]\), \(6\)-й шаг: \([\textbf{1, 4, 6, 5, 2, 3}]\).
-
Если на первом шаге был выбран \(3\)-й камень: \(1\)-й шаг: \([1, 4, \textbf{6}, 5, 2, 3]\), \(2\)-й шаг: \([1, \textbf{4, 6}, 5, 2, 3]\), \(3\)-й шаг: \([\textbf{1, 4, 6}, 5, 2, 3]\), \(4\)-й шаг: \([\textbf{1, 4, 6, 5}, 2, 3]\), \(5\)-й шаг: \([\textbf{1, 4, 6, 5, 2}, 3]\), \(6\)-й шаг: \([\textbf{1, 4, 6, 5, 2, 3}]\).
-
Если на первом шаге был выбран \(4\)-й камень: \(1\)-й шаг: \([1, 4, 6, \textbf{5}, 2, 3]\), \(2\)-й шаг: \([1, 4, 6, \textbf{5, 2}, 3]\), \(3\)-й шаг: \([1, 4, 6, \textbf{5, 2, 3}]\), \(4\)-й шаг: \([1, 4, \textbf{6, 5, 2, 3}]\), \(5\)-й шаг: \([1, \textbf{4, 6, 5, 2, 3}]\), \(6\)-й шаг: \([\textbf{1, 4, 6, 5, 2, 3}]\).
-
Если на первом шаге был выбран \(5\)-й камень: \(1\)-й шаг: \([1, 4, 6, 5, \textbf{2}, 3]\), \(2\)-й шаг: \([1, 4, 6, 5, \textbf{2, 3}]\), \(3\)-й шаг: \([1, 4, 6, \textbf{5, 2, 3}]\), \(4\)-й шаг: \([1, 4, \textbf{6, 5, 2, 3}]\), \(5\)-й шаг: \([1, \textbf{4, 6, 5, 2, 3}]\), \(6\)-й шаг: \([\textbf{1, 4, 6, 5, 2, 3}]\).
- Если на первом шаге был выбран \(6\)-й камень: \(1\)-й шаг: \([1, 4, 6, 5, 2, \textbf{3}]\), \(2\)-й шаг: \([1, 4, 6, 5, \textbf{2, 3}]\), \(3\)-й шаг: \([1, 4, 6, \textbf{5, 2, 3}]\), \(4\)-й шаг: \([1, 4, \textbf{6, 5, 2, 3}]\), \(5\)-й шаг: \([1, \textbf{4, 6, 5, 2, 3}]\), \(6\)-й шаг: \([\textbf{1, 4, 6, 5, 2, 3}]\).
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