Amazon Execute Processes (a.k.a. AWS Processor)

Tasks run in their original order. Tasks with the same original duration belong to the same group; each time a task runs, the current duration of every other not-yet-run task in its group becomes half of that task's current duration, rounded up. Tasks whose original durations differ but later become equal cannot be grouped.

输入格式

The first line contains n, and the second line contains n initial durations. The import catalog lists n≤100000, and this site extends it to 1≤n≤200000 with durations in 1..10^9.

输出格式

Output a single integer answer.

样例 1

输入：

6
5 5 3 6 5 3

输出：

21

样例 2

输入：

3
1 1 1

输出：

3

样例 3

输入：

3
4 2 4

输出：

8

样例说明

Example 1: the actual times are 5, 3, 3, 6, 2, 2, for a total of 21. Example 2: 1 halved and rounded up is still 1, for a total of 3. Example 3: the three tasks take 4, 2, 2, for a total of 8; the initial 2 is not grouped with the 4 that was later reduced to 2.