Бесі грає в таку гру. Гра починається з послідовності з \(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\).

Формат вхідних даних

Перший рядок містить \(N\).

Наступний рядок містить \(N\) розділених одиночними пробілами цілих чисел, що задають вхідну послідовність.

Формат вихідних даних

Один рядок містить суму.

Приклад вхідних даних

6
1 3 1 2 1 10

Приклад вихідних даних

115

Усього є \(\frac{6\cdot 7}{2}=21\) безперервних підпослідовностей. Наприклад, мінімальна можлива фінальна відповідь для підпослідовності \([1,3,1,2,1]\) є 5 і він може бути отриманий такою послідовністю операцій:

original -> [1,3,1,2,1]
combine 1&3 -> [4,1,2,1]
combine 2&1 -> [4,1,3]
combine 1&3 -> [4,4]
combine 4&4 -> [5]

Далі наведено мінімальну фінальну відповідь для всіх підпослідовностей:

final(1:1) = 1
final(1:2) = 4
final(1:3) = 5
final(1:4) = 5
final(1:5) = 5
final(1:6) = 11
final(2:2) = 3
final(2:3) = 4
final(2:4) = 4
final(2:5) = 5
final(2:6) = 11
final(3:3) = 1
final(3:4) = 3
final(3:5) = 4
final(3:6) = 11
final(4:4) = 2
final(4:5) = 3
final(4:6) = 11
final(5:5) = 1
final(5:6) = 11
final(6:6) = 10

ОЦІНЮВАННЯ:

• У тестах 2-3 \(N\le 300\).
• У тестах 4-5 \(N\le 3000\).
• У тестах 6-8, усі числа не більше \(40\).
• У тестах 9-11, вхідна послідовність незменшується.
• У тестах 12-23 немає додаткових обмежень.