Городки старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму.
Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где‑то раздобыть как можно больше одинаковых деревянных палочек. В распоряжении Тимофея есть палочки‑заготовки из дорогого красного дерева в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить биты.
Если длина палочки является чётным числом d, Тимофей может распилить её пополам и получить две палочки вдвое меньшей длины d2. Если же длина палочки является нечётным числом, Тимофей может распилить её на две части, как можно меньше отличающиеся друг от друга: ⌊d2(d пополам, округлённое вниз до целой части) и ⌈d2⌉ (d пополам, округлённое вверх до целой части). Распиливать уже распиленные ранее палочки Тимофею лень, и он переходит к следующей заготовке. Задача Тимофея получить наибольшее количество бит какого‑нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший.
Формат входных данных
В первой строке входных данных записано одно натуральное число: nn (1≤n≤105) длина самой длинной заготовки.
В следующих nn строках записано по одному натуральному числу didi (0≤di≤109, dn≠0) количество палочек длины i−1. Так, во второй строке записано количество палочек длины 1, в третьей количество палочек длины 2 и так далее. В последней строке записано количество палочек длины nn.
Обратите внимание, что при заданных ограничениях для хранения входных данных и ответа может понадобиться 64‑битный тип данных, например, long long в C++, int64 в Free Pascal, long в Java.
Формат выходных данных
Выведите в двух строках два натуральных числа наибольшее количество получившихся палочек одного размера и сам этот размер.
Система оценки
Решения, верно работающие при n≤3, получат не менее 30 баллов.
Решения, верно работающие при n≤1000, получат не менее 70 баллов.
Замечание
У Тимофея есть несколько палочек, самая длинная имеет длину 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