Олимпиада по информатике

Городки

Городки старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму.

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

какого‑нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший.

Формат входных данных

В первой строке входных данных записано одно натуральное число: nn (1≤n≤105) длина самой длинной заготовки.

В следующих nn строках записано по одному натуральному числу didi (0≤di≤109, dn≠0) количество палочек длины i−1. Так, во второй строке записано количество палочек длины 1, в третьей количество палочек длины 2 и так далее. В последней строке записано количество палочек длины nn.

Замечание

У Тимофея есть несколько палочек, самая длинная имеет длину 5. Более точно:

Нет палочек длины 1;

Одна палочка длины 2;

Нет палочек длины 3;

Одна палочка длины 4;

Две палочки длины 5.

Тимофей распилит пополам палочку длины 4 и получит две палочки длины 2. Также он распилит обе палочки длины 5 и получит две палочки длины 2 и две палочки длины 3. Вместе с имеющейся у него одной исходной палочкой длины 2 (её Тимофей пилить не будет) в его распоряжении окажется пять одинаковых палочек длины 2. Это наилучший результат, который может получить Тимофей (наибольшее количество палочек длины 1, которое можно получить из исходного набора, равно двум; палочек длины 3 двум; палочек длины 4 одному; палочек длины 5 двум).

Ввод

5

0

1

0

1

2

Вывод

5

2