Беси играет в такую игру.
Игра начинается с последовательности из \(N\) (\(2\le N\le 262,144\)) положительных
целых чисел \(a_1,a_2,\ldots,a_N\), каждое в интервале \(1\ldots 10^6\).
За один ход Беси может взять два соседних числа и заменить их на число, большее,
чем максимум из этих двух чисел (например, соседнюю пару \((5,7)\) на \(8\)).
Игра заканчивается после \(N-1\) ходов, после которых остаётся только одно число.
Цель игры - минимизировать это финальное число.
Ваша задача сыграть оптимально не только для \(a\), но и для всех непрерывных
подпоследовательностей \(a\).
Выведите сумму минимально возможных финальных чисел для всех \(\frac{N(N+1)}{2}\)
непрерывных подпоследовательностей \(a\).
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Следующая строка содержит \(N\) разделённых одиночными пробелами целых чисел,
задающих входную последовательность.
ФОРМАТ ВЫВОДА (на экран / stdout):
Одна срока, содержащая сумму.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1 3 1 2 1 10
|
115
|