Назовем массив \(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 массивом.
Выходные данные
Выведите количество пар целых чисел \((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.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
2 3 1
|
6
|
|
2
|
6
4 5 2 6 1 3
|
19
|
|
3
|
10
7 10 1 8 3 9 2 4 6 5
|
39
|