Задача Двуствольная пушка (DGUN)

Цель компьютерной игры WALLCRSH – разбить все плиты, укреплённые на стенах оборонной башни противника. Башня имеет вид правильного многоугольника с N вершинами (т.е. каждая стена башни является стороной многоугольника). Для разрушения плит игрок использует специальную двуствольную пушку, каждый выстрел которой разрушает (в зависимости от желания игрока) либо две плиты на одной и той же стене башни, либо по одной плите на двух соседних стенах. Стрельба по стенам, на которых не осталось плит, не запрещается, но это считается расточительством.

Найдите, за какое минимальное количество выстрелов можно разрушить все плиты.

Формат ввода/вывода:

Напишите программу DGUN, которая читает входные данные из файла DGUN.DAT и записывает ответ в файл DGUN.SOL. В первой строке файла DGUN.DAT находится количество стен, во второй – разделённые пробелами количества плит на каждой стене .

Файл DGUN.SOL должен содержать единственное число – минимальное количество выстрелов.

Ограничения: ,  .

Пример: