D. Разбиение на возрастающую и спадающую
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Назовем массив $$$a$$$ из $$$m$$$ целых чисел $$$a_1, a_2, \ldots, a_m$$$ Decinc, если $$$a$$$ можно сделать возрастающим, удалив из него убывающую подпоследовательность (возможно, пустую).

  • Например, если $$$a = [3, 2, 4, 1, 5]$$$, мы можем удалить из $$$a$$$ убывающую подпоследовательность $$$[a_1, a_4]$$$ и получить $$$a = [2, 4, 5]$$$, которая является возрастающей.

Вам дана перестановка $$$p$$$ чисел от $$$1$$$ до $$$n$$$. Найдите количество пар целых чисел $$$(l, r)$$$ с $$$1 \le l \le r \le n$$$ таких, что $$$p[l \ldots r]$$$ (подмассив $$$p$$$ от $$$l$$$ до $$$r$$$) является Decinc массивом.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)  — размер $$$p$$$.

Вторая строка содержит $$$n$$$ целых $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$, все $$$p_i$$$ различны)  — элементы перестановки.

Выходные данные

Выведите количество пар целых чисел $$$(l, r)$$$ таких, что $$$p[l \ldots r]$$$ (подмассив $$$p$$$ от $$$l$$$ до $$$r$$$) является Decinc массивом. $$$(1 \le l \le r \le n)$$$

Примеры
Входные данные
3
2 3 1
Выходные данные
6
Входные данные
6
4 5 2 6 1 3
Выходные данные
19
Входные данные
10
7 10 1 8 3 9 2 4 6 5
Выходные данные
39
Примечание

В первом примере все подмассивы являются Decinc.

Во втором примере все подмассивы, кроме $$$p[1 \ldots 6]$$$ и $$$p[2 \ldots 6]$$$ являются Decinc.