E. Хорошие подотрезки
ограничение по времени на тест
7 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановкой $$$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]$$$ хорошими подотрезками являются:

  • $$$[1, 1]$$$,
  • $$$[1, 3]$$$,
  • $$$[1, 5]$$$,
  • $$$[2, 2]$$$,
  • $$$[2, 3]$$$,
  • $$$[2, 5]$$$,
  • $$$[3, 3]$$$,
  • $$$[4, 4]$$$,
  • $$$[4, 5]$$$,
  • $$$[5, 5]$$$.

Дана перестановка $$$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