Перестановкой \(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\).
Выходные данные
Выведите \(q\) строк, \(i\)-я из них должна содержать количество хороших подотрезков отрезка, данного в \(i\)-м запросе.