Азартный плотник
(Время: 1 сек. Память: 16 Мб Сложность: 15%)
Однажды плотник Андрей поспорил с друзьями на то, что он сможет вбить N гвоздей в ряд за пару часов. Он знал на что шёл и поэтому выиграл спор! Однако, после он понял, что зря это сделал и теперь ему придется выдергивать все вбитые гвозди.
Пронумеруем все вбитые гвозди числами от 1 до N. Для всех гвоздей определены параметры: a1, a2, ..., aN. Известно, что для извлечения гвоздя с номером i понадобится минимум из ai-1 и ai+1 секунд (извлечение первого гвоздя требует a2 секунд времени, а на извлечение последнего уйдет aN-1 секунд). Также известно, что когда останется лишь один гвоздь, то он выпадет сам мгновенно. После извлечения гвоздя с номером i остальные гвозди заново перенумеровываются.
Андрей хочет как можно меньше потратить времени на работу с выдергой и просит Вас помочь ему оптимизировать его работу. Определите, за какое минимальное время он сможет выдернуть все гвозди. Андрей может выдергивать гвозди в любом порядке.
Входные данные
В первой строке входного файла INPUT.TXT записано одно целое число N (1 ≤ N ≤ 105) – количество вбитых гвоздей.
В каждой из следующих N строк записано по одному целому числу ai (1 ≤ ai ≤ 104) – параметр для гвоздя с номером i.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно целое число – минимальное время, которое понадобится Андрею для извлечения всех гвоздей.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
1
2
3
1
100 | 4 |
| 2 | 1
1 | 0 |
Пояснение к примерам
В первом примере Андрей вбил 5 гвоздей с параметрами 1, 2, 3, 1 и 100. Один из оптимальных вариантов последовательности его действий приведен ниже:
- Извлекаем последний гвоздь. На это уйдет 1 секунда.
- Затем извлечем гвоздь с параметром 2 за одну секунду.
- Далее выдернем гвоздь с параметром 3 за одну секунду.
- Извлечем любой из оставшихся гвоздей за секунду.
- Последний гвоздь выпадет сам.
Итого, Андрею понадобится произвести 4 операции по извлечению гвоздя, каждая из которых занимает одну секунду, таким образом общее время работы – 4 секунды.
Во втором примере у Андрея изначально всего один гвоздь, который сразу же выпадет сам.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
