Codeforces Round 493 (Div. 1) |
---|
Закончено |
Перестановкой $$$p$$$ длины $$$n$$$ назовем последовательность $$$p_1, p_2, \ldots, p_n$$$, состоящую из $$$n$$$ различных целых чисел, каждое из которых от $$$1$$$ до $$$n$$$ ($$$1 \leq p_i \leq n$$$).
Назовем подотрезок $$$[l,r]$$$ перестановки хорошим, если среди чисел $$$p_l, p_{l+1}, \dots, p_r$$$ встречаются все числа от минимума на нем до максимума на этом подотрезке.
Например, у перестановки $$$[1, 3, 2, 5, 4]$$$ хорошими подотрезками являются:
Дана перестановка $$$p_1, p_2, \ldots, p_n$$$.
Требуется ответить на $$$q$$$ запросов вида: найдите количество хороших подотрезков данного отрезка перестановки.
Иными словами, для ответа на один запрос вам требуется для некоторого заданного отрезка $$$[l \dots r]$$$ посчитать количество таких хороших подотрезков $$$[x \dots y]$$$, что $$$l \leq x \leq y \leq r$$$.
В первой строке записано единственное целое число $$$n$$$ ($$$1 \leq n \leq 120000$$$) — количество элементов в перестановке.
Во второй строке записаны $$$n$$$ различных целых чисел $$$p_1, p_2, \ldots, p_n$$$, разделенных пробелами ($$$1 \leq p_i \leq n$$$).
В третьей строке записано целое число $$$q$$$ ($$$1 \leq q \leq 120000$$$) — количество запросов.
Следующие $$$q$$$ строк описывают запросы, каждая из них содержит пару целых чисел $$$l$$$, $$$r$$$, разделенных пробелом ($$$1 \leq l \leq r \leq n$$$).
Выведите $$$q$$$ строк, $$$i$$$-я из них должна содержать количество хороших подотрезков отрезка, данного в $$$i$$$-м запросе.
5
1 3 2 5 4
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5
1
2
5
6
10
1
3
4
7
1
2
4
1
3
1
Название |
---|