**Замечание: Время на тест 3 сек, в 1.5 больше чем по умолчанию .**
Вам дан целочисленный массив длины \(N\): \(a_1,a_2,\dots,a_N\)
(\(2\le N\le 10^6, 1\le a_i\le N\)).
Выведите сумму ответов для подзадачи ниже по всем \(N(N+1)/2\)
непрерывным подмассивам массива \(a\).
По заданному непустому списку целых чисел чередуйте следующие операции
(начиная с первой операции) пока в списке останется ровно одно число.
- Замените два последовательных целых числа на их минимум.
- Замените два последовательных целых числа на их максимум.
Определите максимально возможное значение оставшегося числа.
Например,
[4, 10, 3] -> [4, 3] -> [4]
[3, 4, 10] -> [3, 10] -> [10]
В первом массиве, \((10, 3)\) заменяется на \(\min(10, 3)=3\) и
\((4, 3)\) заменяется на \(\max(4, 3)=4\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Вторая строка содержит \(a_1,a_2,\dots,a_N\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Сумма ответов на подзадачу по всем подмассивам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2 1
|
4
|