Задача №111880. Скайлайн
Вы хотите, чтобы небоскребы в вашем городе имели красивый вид. Решено построить N небоскребов в ряд. У небоскреба с номером \(i\) должно быть ровно \(h[i]\) этажей.
У Вас есть предложения от различных строительных компаний. Первая из них предлагает строить один этаж в любом из небоскребов за 3 миллиона евро. Вторая предлагает строить по одному этажу в каждом из двух соседних небоскребов за 5 миллионов евро. Заметим, что не имеет значения, находятся ли эти этажи на одинаковой высоте или нет. Третья компания предлагает строить по одному этажу в каждом из трех последовательных небоскребах за 7 миллионов евро.
Вы можете построить этажи в любом порядке. Вычислите минимальную необходимую сумму денег для строительства.
Первая строка содержит одно целое число \(N\) (1 \(\le\) \(N\) \(\le\) 300). Вторая строка содержит \(N\) целых чисел h[1], h[2] ..., h[N], 1 \(\le\) h[i] \(\le\) 200.
В единственной строке выведите одно целое число: минимальную сумму денег для строительства, в миллионах.
3 2 2 2
14
4 1 3 1 1
15