У Артема есть массив из n целых положительных чисел. Артем решил с ним поиграть. Игра состоит из n ходов. Каждый ход происходит следующим образом. Артем выбирает некоторый элемент массива и удаляет его. За это он получает min(a, b) очков, где a и b — числа, которые были соседями удаленного числа. Если у него нет левого или правого соседа, то Артем не получает никаких очков.
После удаления элемента две части массива склеиваются и получается новый массив, с которым и продолжает играть Артем. Боре стало интересно, какое максимальное суммарное количество очков может получить Артем, играя в эту игру.
Выходные данные
В единственной строке выведите одно число — максимальное количество очков, которые может получить Артем.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3 1 5 2 6
|
11
|
|
2
|
5
1 2 3 4 5
|
6
|
|
3
|
5
1 100 101 100 1
|
102
|