Знаете ли вы, что некоторые студенты, вместо того, чтобы учиться, участвуют в разных соревнованиях? Иногда такие студенты даже получают дипломы за победы в этих соревнованиях. А знаете ли вы, что некоторые деканы собирают и развешивают на стене
деканата цветные копии студенческих дипломов? Вы не поверите, но когда дипломов накапливается много, иногда в деканате ставят дополнительные стенки! Но прежде чем поставить очередную стенку, надо определить ее размер. А для этого нужен проект размещения дипломов на стене. Поэтому нанимают дизайнера — чтобы все было красиво.
И вот последний нанятый дизайнер заявил, что все дипломы одного типа (например, за полуфинальные соревнования) должны висеть в одном ряду. И не как попало, а симметрично относительно центра стены. И чтобы больше в этом ряду ничего не висело. Но секретарь резонно заметила, что типов дипломов много, и в таком случае высоты стены может просто не хватить. Тогда дизайнер согласился, что вперемешку с дипломами одного типа можно повесить дипломы другого типа. Но в одном ряду уж точно не должно быть больше двух типов дипломов. И обязательно надо чтобы было строгое чередование этих двух типов внутри ряда. И чтоб сохранялась симметрия относительно центра.
Никому не охота ломать голову, что же все эти требования означают, поэтому декан и поручил развешивание самим студентам. Пока строители не ушли, вам нужно найти минимально возможное количество рядов, в которые можно разместить все дипломы, не
нарушая требований дизайнера. В случае чего, придется поставить еще несколько стенок. Можно считать, что в ширину стены деканата бесконечны.
Исходные данные
В первой строке находится число N (1 ≤ N ≤ 18) — количество разных типов дипломов. Во второй строке через пробел выписаны количества дипломов каждого типа, N чисел не меньших 1 и не превосходящих 30.
Результат
Вывести минимальное количество рядов, в которые можно разместить все
дипломы в соответствии с требованиями дизайнера.
Пример
исходные данные | результат |
---|
6
8 15 13 8 14 8 | 5 |
Автор задачи: Станислав Васильев
Источник задачи: Седьмое открытое личное первенство УрГУ по спортивному программированию - 25 февраля 2006 года