Codeforces Round 800 (Div. 1) |
---|
Закончено |
Назовем массив $$$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)$$$
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.
Название |
---|