409361: GYM103491 C Flynn's cars

C. Машинкиограничение по времени на тест0.7 секундограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Федя очень любит играть в машинки-трансформеры. В этой игре побеждает тот игрок, у которого самая быстрая машинка. Чтобы увеличить скорость машины, можно выбрать другую машинку с такой же скоростью, разобрать, а затем их обе объединить в одну, со скоростью, которая в два раза больше изначальной. Также игра позволяет разобрать машину с четной скоростью и собрать из нее две со скоростью в два раза меньшей.

Вам даны машинки, которые есть у Феди. Он очень хочет узнать, какая самая максимальная скорость может быть у машинки, которую он уже имеет или может собрать.

Входные данные

В первой строке вводится одно число $$$1 \leq n \leq 10^5$$$ – количество машинок у Феди.

Во второй строке через пробел вводится массив $$$a$$$, состоящий из $$$n$$$ неотрицательных чисел, в сумме не превосходящих $$$10^{15}$$$, – скорости машинок, которые изначально были у Феди.

Выходные данные

Он очень хочет узнать, какая максимальная скорость может быть у машинки, которую он может собрать или которая у него уже имеется.

Система оценки

В данной задаче 25 тестов (помимо тестов из условия), каждый из них оценивается в 4 балла.

Решения, корректно работающие при всех $$$a_i$$$, равных степеням двоек, наберут не менее 36 баллов.

Решения, корректно работающие при $$$1 \leq n \leq 100$$$ и $$$(\sum_{i=1}^{i \le n}{a_i}) \leq 10^5$$$, наберут не менее 52 баллов.

ПримерыВходные данные

5
3 5 6 20 6

Выходные данные

20

Входные данные

6
2 0 8 4 8 16

Выходные данные

32