Назовем массив \(a\) из \(m\) целых чисел \(a_1, a_2, \ldots, a_m\) Decinc, если \(a\) можно сделать возрастающим, удалив из него убывающую подпоследовательность (возможно, пустую).
Вам дана перестановка \(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)\)
В первом примере все подмассивы являются Decinc.
Во втором примере все подмассивы, кроме \(p[1 \ldots 6]\) и \(p[2 \ldots 6]\) являются Decinc.
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
2000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач