Знаете ли вы, что некоторые студенты, вместо того, чтобы учиться, участвуют в разных соревнованиях? Иногда такие студенты даже получают дипломы за победы в этих соревнованиях. А знаете ли вы, что некоторые деканы собирают и развешивают на стене деканата цветные копии студенческих дипломов? Вы не поверите, но когда дипломов накапливается много, иногда в деканате ставят дополнительные стенки! Но прежде чем поставить очередную стенку, надо определить ее размер. А для этого нужен проект размещения дипломов на стене. Поэтому нанимают дизайнера — чтобы все было красиво.

И вот последний нанятый дизайнер заявил, что все дипломы одного типа (например, за полуфинальные соревнования) должны висеть в одном ряду. И не как попало, а симметрично относительно центра стены. И чтобы больше в этом ряду ничего не висело. Но секретарь резонно заметила, что типов дипломов много, и в таком случае высоты стены может просто не хватить. Тогда дизайнер согласился, что вперемешку с дипломами одного типа можно повесить дипломы другого типа. Но в одном ряду уж точно не должно быть больше двух типов дипломов. И обязательно надо чтобы было строгое чередование этих двух типов внутри ряда. И чтоб сохранялась симметрия относительно центра.

Никому не охота ломать голову, что же все эти требования означают, поэтому декан и поручил развешивание самим студентам. Пока строители не ушли, вам нужно найти минимально возможное количество рядов, в которые можно разместить все дипломы, не нарушая требований дизайнера. В случае чего, придется поставить еще несколько стенок. Можно считать, что в ширину стены деканата бесконечны.

В первой строке находится число N (1 ≤ N ≤ 18) — количество разных типов дипломов. Во второй строке через пробел выписаны количества дипломов каждого типа, N чисел не меньших 1 и не превосходящих 30.

Вывести минимальное количество рядов, в которые можно разместить все дипломы в соответствии с требованиями дизайнера.