Calculate Leftover Stacks

Process the piles from left to right: every two blocks combine into one block that is added to the pile on the right, and the current pile keeps at most one block. Carrying continues past the end of the original array until no more merges are possible. Find the number of piles that end up with one block.

输入格式

This site's input: the first line contains n (1..100000), and the second line contains n block counts (0..10⁹).

输出格式

Output a single integer, the answer.

样例 1

输入：

3
5 3 1

输出：

4

样例 2

输入：

1
0

输出：

0

样例 3

输入：

1
2

输出：

1

样例说明

Example 1: the totals pile by pile are 5, 5, 3, and each keeps 1; at the end carry=1 keeps 1 more, for a total of 4.

Example 2: there are no blocks, so the answer is 0.

Example 3: two blocks combine into one to the right, leaving only 1 pile.