E. Scored Nim
time limit per test
2 seconds
memory limit per test
512 mebibytes
input
standard input
output
standard output

Alice and Bob want to play Nim. Well, some kind of it.

Initially, they have $$$n$$$ heaps of stones, $$$i$$$-th heap containing $$$a_i$$$ stones. Players take alternating turns, Alice moves first. On their turn, a player chooses any heap with at least two stones and splits it into two new heaps with at least one stone in each. After that, the player colors all stones in one of the new heaps white and all stones in the other one black. The game lasts until every heap contains only one stone.

After the game, Alice's score is the number of white stones on the board, and Bob's score is the number of black stones. Both players want to maximize their score and play optimally. What will be Alice's score?

Input

The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 128$$$).

The second line of input contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$2 \leq a_i \leq 128$$$).

Note that the initial colors of the stones are irrelevant.

Output

Output a single integer: Alice's score if both players play optimally.

Example
Input
2
2 2
Output
2
Note

In the example, no matter how players move, both heaps will be split between them equally.