Задача №3199. Делёж яблок
Этим летом у бабушки был большой урожай яблок. Она собрала яблоки в корзину и отдала своим \(K\) внукам.
Первый внук взял из корзины половину всех яблок и еще \(a_1\) яблоко (если количество яблок не делилось на два, то результат деления на два он мог округлить как в большую сторону, так и в меньшую). К примеру, если в корзине было 7 яблок и \(a_1 = 1\), то он мог взять либо 4, либо 5, а если было 6 яблок и \(a_1 = 1\), то он взял ровно 4.
Второй внук взял половину от всех оставшихся яблок и ещё \(a_2\) (если яблок было нечетное количество, то он также мог округлить половину как в большую, так и в меньшую сторону). И так далее, \(K\)-ый внук взял половину яблок, оставшихся после \(K - 1\) внука, и ещё \(a_k\). В итоге в корзине ничего не осталось.
Теперь они задумались, насколько же большой урожай был у бабушки. Ни один из них не помнит, делилось ли количество яблок на 2 нацело при его выборе, а если нет, то в какую сторону он округлил половину яблок. Внуков интересует минимальное и максимальное изначальное количество яблок в корзине, при которых могли произойти описанные события.
Сначала вводится целое положительное число \(K\) (\(1 \le K \le 1\,000\)). Далее записано \(K\) целых неотрицательных чисел \(a_1, \dots , a_K\) (\(0 \le a_i \le 1\,000\)).
Выведите два неотрицательных целых числа без ведущих нулей, каждое в новой строке - минимальное и максимальное возможное количество яблок в корзине соответственно.
1 1
1 3
2 0 1
1 7