Задача: Удаление данных

Случилась беда — шпиона Сергея раскрыли, и теперь ему нужно срочно бежать! Но перед побегом он должен удалить все компрометирующие данные со своего компьютера.
На компьютере Сергея сохранены N файлов, пронумерованных числами от 1 до N. У каждого из файлов есть размер в байтах: a₁, a₂, . . . , a_N. Все данные на компьютере Сергея хорошо зашифрованы. Шпион определил, что для удаления файла с номером i понадобится минимум из a_i−1 и a_i+1 секунд (для удаления первого файла потребуется a₂ секунд, а для удаления последнего — a_N−1 секунд). Когда остается всего один файл, он удаляется мгновенно. После удаления файла с номером i остальные файлы перенумеровываются последовательно.
У Сергея осталось очень мало времени, а ему еще нужно собрать вещи, поэтому он просит у вас помощи. Определите, какое минимальное время понадобится шпиону, чтобы удалить все файлы.
Сергей может удалять файлы последовательно в любом порядке.

Входные данные
В первой строке выходных данных записано одно целое число N (1 ≤ N ≤ 10⁵) — количество файлов на компьютере шпиона.
В каждой из следующих N строк записано по одному целому числу a_i (1 ≤ a_i ≤ 10⁴) — размер файла с номером i на компьютере Сергея.

Выходные данные
В единственной строке выведите одно число — минимальное время, которое понадобится Сергею для удаления всех файлов.
 

Примеры

№	Входные данные	Выходные данные
1	5 1 2 3 1 100	4
2	1 1	0

Замечание
В первом примере у Сергея есть файлы с размерами 1, 2, 3, 1, 100. Один из вариантов решения приведен ниже:
1. Удалим последний файл. Это займет одну секунду.
2. Затем удалим файл размера 2 за одну секунду.
3. Далее удалим файл размера 3 за одну секунду.
4. Теперь удалим любой из оставшихся двух файлов за одну секунду.
5. Последний файл моментально удалится сам.
Итого, Сергею понадобится 1 + 1 + 1 + 1 = 4 секунды.
Во втором примере у Сергея изначально есть всего один файл, который сразу же удалится.
 

           

Ваш ответ: