Sticks

Time limit1sMemory limit128 MB

Summary

Given stick lengths, repeatedly merge pairs of equal length into doubled sticks and report how many distinct sticks remain.

Level: Easy3 of 10
Topics: Hash map, Array, Simulation
Solved: No attempts yet

Problem

You are given a collection of sticks whose lengths are positive integers. Any two sticks that have the same length can be glued together into a single stick whose length is twice as long. Keep gluing sticks together as long as two sticks share a length, that is, until every remaining stick has a distinct length. How many sticks are left at the end?

Input

The first line contains the number of sticks $n$ ( $1 \le n \le 100\,000$ ). The second line contains $n$ integers, the lengths of the sticks, where every length is between $1$ and $1000$ inclusive.

Output

Print the number of sticks that remain after all sticks of equal length have been glued together.

Examples3

Example 1
Input
```
10
3 3 3 3 3 3 3 3 3 3
```
Expected output
```
2
```
Example 2
Input
```
1
7
```
Expected output
```
1
```
Example 3
Input
```
5
1 2 3 4 5
```
Expected output
```
5
```