ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1152. Кривые зеркала

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ

Вступление

Мы блуждаем по зеркальному лабиринту минут двадцать, и, наконец, выходим в большой зал. Тоже зеркальный. А под потолком — балкончики, на которых стоят монстры. Таких я ещё не видел — огромные выпуклые глаза, длинные руки, цепко сжимающие винтовки, чешуйчатое тело. В остальном — вполне человекообразные… Гвардия палит в меня с балкончиков, я тоже стреляю. «BFG-9000» выжигает три зеркала одним залпом. Помещение наполнено серебряным дымом. Пули колотят по броне, сбивая меня на пол. Стреляю в падении, вращаюсь на спине словно в забытом танце своей юности — «брейке», ещё два раза стреляю. Три зеркала, три зеркала, три зеркала…
Сергей Лукьяненко, «Лабиринт отражений»

Задача

За один залп BFG-9000 уничтожает три соседних балкончика. (N-й балкончик соседствует с первым). После залпа оставшиеся в живых монстры наносят Леониду (главному герою романа) повреждения — по одной единице каждый. Далее следует новый залп и так до тех пор, пока все монстры не погибнут. Требуется определить минимальные повреждения, которые может понести Леонид.

Исходные данные

Первая строка содержит целое число N, количество балкончиков, на которых монстры заняли круговую оборону. 3 ≤ N ≤ 20. Во второй строке даны N целых чисел, количества монстров на каждом балкончике (на каждом не менее 1 и не более 100).

Результат

Выведите минимальное количество единиц повреждений

Пример

исходные данныерезультат
7
3 4 2 2 1 4 1
9
Автор задачи: Евгений Брызгалов
Источник задачи: Командный чемпионат Урала по программированию. Пермь, апрель 2001 г., английский тур.