E. Ewo Slices of Bread with Cheese
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

During the May Day holiday, Tryna went to visit the dentist. Unfortunately, his dentist was a so beautiful girl that he spent a lot of money in pleasing her. Now he has to have two slices of bread with cheese for breakfast for the rest of the month.

Worse, Tryna went to the supermarket and bought too much cheese. The $$$i$$$-th piece of cheese has the freshness $$$a_i$$$. The freshness of cheese will be reduced by $$$1$$$ every day, and Tryna can eat one piece of cheese at most in a day. Because of Tryna's special hobby, he will only choose the cheese whose freshness can be divided by two to eat.

Now Tryna is wondering how long does it take him to finish all the cheese at least.

Input

The first line contains $$$1$$$ integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the amount of cheese Tryna bought.

The next line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, $$$\dots$$$, $$$a_n$$$ ($$$5 \cdot 10^5\leq a_i \leq 10^6$$$) — the freshness of the cheese.

Output

Print the minimum number of days Tryna need to finish all the cheese at least.

Examples
Input
4
500001 500002 500003 500004
Output
4
Input
2
500001 500003
Output
4
Input
2
500004 500002
Output
3
Note

In the first example, one possible situation is as follows:

  • In the first day, Tryna take the second piece of cheese, then the freshness array = $$$[500001$$$,$$$500003$$$,$$$500004]$$$.
  • In the next day, the array = $$$[500000$$$,$$$500002$$$,$$$500003]$$$. Tryna take the first piece of cheese, then the arrry = $$$[500002$$$,$$$500003]$$$.
  • The rest is the same as above.

In the second example, one possible situation is as follows:

  • In the first day, Tryna can't take any piece of cheese since no piece of cheese's freshness can be divided by two.
  • In the next day, the array = $$$[500000$$$,$$$500002]$$$. Tryna take the first piece of cheese, then the array = $$$[500002]$$$.
  • The rest is the same as above.