C. Sorting Subarrays
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел. Вы должны ровно один раз применить к этому массиву операцию сортировки подотрезка, то есть выбрать какой-то непустой подотрезок массива и переупорядочить элементы этого подотрезка в неубывающем порядке.

Сколько различных массивов вы можете получить в результате такой операции? Подотрезком массива называются несколько подряд идущих элементов массива.

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

Первая строка содержит число $$$n$$$ — размер массива ($$$1 \le n \le 200\,000$$$).

Вторая строка содержит $$$n$$$ целых чисел $$$a_1$$$, $$$a_2$$$, ... $$$a_n$$$ — элементы массива ($$$1 \le a_i \le 10^9$$$).

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

Выведите количество различных массивов, которое можно получить после применения одной операции сортировки подотрезка.

Система оценки
ПодзадачаБаллыОграничения
113$$$n \le 50$$$
226$$$n \le 3\,000$$$
322$$$1 \le a_i \le 2$$$
439Без дополнительных ограничений
Примеры
Входные данные
7
3 1 4 1 5 9 2
Выходные данные
8
Входные данные
4
1 2 3 4
Выходные данные
1
Примечание

Ниже перечислены все возможные различные массивы, которые можно получить в первом примере, и один из способов получить каждый из них. Сортируемые подотрезки отмечены квадратными скобками.

  1. $$$[3], 1, 4, 1, 5, 9, 2 \rightarrow 3, 1, 4, 1, 5, 9, 2$$$
  2. $$$[3, 1], 4, 1, 5, 9, 2 \rightarrow 1, 3, 4, 1, 5, 9, 2$$$
  3. $$$[3, 1, 4, 1], 5, 9, 2 \rightarrow 1, 1, 3, 4, 5, 9, 2$$$
  4. $$$[3, 1, 4, 1, 5, 9, 2] \rightarrow 1, 1, 2, 3, 4, 5, 9$$$
  5. $$$3, [1, 4, 1], 5, 9, 2 \rightarrow 3, 1, 1, 4, 5, 9, 2$$$
  6. $$$3, [1, 4, 1, 5, 9, 2] \rightarrow 3, 1, 1, 2, 4, 5, 9$$$
  7. $$$3, 1, 4, [1, 5, 9, 2] \rightarrow 3, 1, 4, 1, 2, 5, 9$$$
  8. $$$3, 1, 4, 1, 5, [9, 2] \rightarrow 3, 1, 4, 1, 5, 2, 9$$$