Федя очень любит играть в машинки-трансформеры. В этой игре побеждает тот игрок, у которого самая быстрая машинка. Чтобы увеличить скорость машины, можно выбрать другую машинку с такой же скоростью, разобрать, а затем их обе объединить в одну, со скоростью, которая в два раза больше изначальной. Также игра позволяет разобрать машину с четной скоростью и собрать из нее две со скоростью в два раза меньшей.
Вам даны машинки, которые есть у Феди. Он очень хочет узнать, какая самая максимальная скорость может быть у машинки, которую он уже имеет или может собрать.
В первой строке вводится одно число $$$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
| 1 Олимпиада Силаэдра |
|---|
| Закончено |
