View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem type

Larry is taking the SAT! However, because Larry is :larrycreep:, the SAT changed their scoring system. Every SAT test has different questions, each with a different point value. The first question is worth 1 point, and each subsequent question is worth twice the previous question. Larry's score is the sum of the marks of all the questions he got right, and he is unable to get part marks for these questions (0 marks for wrong answers).

Larry did really poorly on N of his exams, so to get into university he used his :larrycreep: powers to rig the system. Instead, he'll send them his SAT superscore. The SAT superscore is calculated by taking the highest mark received for each question, and summing them up. However, if Larry gets a score of at least 10^9, he'll get accepted anyways, so the superscore will be 10^9. Given the marks from Larry's exams, can you find the superscore?

Input Specification

The first line will contains the integer N\ (1 \le N \le 10^5). The next N lines will contain an integer x\ (0 \le x \le 2^{60}), representing Larry's score on one of his exams.

Output Specification

Print Larry's superscore, on one line.


Subtask 1 [10%]

x \le 1

Subtask 2 [90%]

No further constraints.

Note: You do not need to pass the sample for subtask 1.

Sample Input


Sample Output


Sample Explanation

On his first exam, Larry gets no questions correct. On his second exam, Larry gets the first and second questions right. On the third exam, Larry gets the third question right. Therefore, his superscore is 1 + 2 + 4 = 7.


There are no comments at the moment.