Ограничения: время – 200ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Рассмотрим все возможные подсписки списка из `N` элементов. Подсписком называется часть списка с `i`-го до `j`-го элемента, где `1 <= i<=j <= N`.
В каждом подсписке найдем минимальное значение.
Например, для списка [3,1,2,5] получаются следующие подсписки и их минимумы.
Подсписок|Минимум
---------|-------
[3]|3
[3,1]|1
[3,1,2]|1
[3,1,2,5]|1
[1]|1
[1,2]|1
[1,2,5]|1
[2]|2
[2,5]|2
[5]|5
Сумма минимумов по всем возможным подспискам равна `3+1+1+1+1+1+1+2+2+5=18`.
Напишите программу, которая находит сумму минимумов по всем возможным подспискам
для заданного списка из `N` элементов.
Первая строка ввода содержит одно целое число `N` (`1 <= N <= 35000`) -- количество элементов в списке.
Следующие `N` строк содержат по одному целому числу `A_i` (`1 <= A_i <= 10000`) -- элементы списка.
Вывести одно целое число -- сумму минимумов.
```sample Пример ввода
4
3
1
2
5
```
```sample Пример вывода
18
```
*Система оценки и описание подзадач*
||.u|Подзадача 1 (30 баллов)||
`1 <= N <= 100`, `1 <= A_i <= 100`
В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 2 (40 баллов)||
`100 <= N <= 2000`, `1 <= A_i <= 1000`
Необходимые подзадачи: 1.
В этой подзадаче 4 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
||.u|Подзадача 3 (30 баллов)||
`2000 <= N <= 35000`, `1 <= A_i <= 10000`
Необходимые подзадачи: 1, 2.
В этой подзадаче 3 теста. Баллы за подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.
Начало
Рабочее место участника
Сокращение перебора с помощью идеи