408401: GYM103114 E Ewo Slices of Bread with Cheese

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.

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.

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

4
500001 500002 500003 500004

4

2
500001 500003

4

2
500004 500002

3

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.