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