Problem A
The Paw-litical Game

The country Gattekatt has a very unusual shape. It is extremely elongated, resulting in its $N$ cities each occupying an interval of the country. The cities are numbered from $1$ to $N$, from left to right. Each city has a population of cats. Interestingly, the number of cats is always equal to $2^ k$ for some integer $k$ (there are a lot of cats in Gattekatt). To prepare the country for a potential rat invasion, the government wants as many cities as possible to unite. Unfortunately, the cities are very picky about who they are willing to cooperate with. For two cities $a$ and $b$ to unite, the following conditions are required:

• The cities $a$ and $b$ are adjacent.

• The number of cats in city $a$ and city $b$ is exactly the same. This is because the number of cats in the city is directly correlated with the city’s political influence, and a city won’t consider cooperating with a city it perceives as having less political influence.

When two adjacent cities $a$ and $b$, each with $2^ k$ cats decide to unite, they form a single city with a cat population of $2^{k+1}$. The new city can then potentially unite with the city to the left of $a$ or the city to the right of $b$.

Top politicians from Gattekatt now want your help in calculating the minimum number of cities that can remain in the end if the cities are united in an optimal order.

Input

The first line of input contains the integer $N$ ($1 \leq N \leq 10^6$).

The second line of input contains $N$ integers $k_1, k_2, \dots , k_ N$ ($1 \leq k_ i \leq 10^9$). Each $k_ i$ means that city $i$ has $2^{k_ i}$ cats as inhabitants.

Output

Print an integer: the least number of cities that can remain if the cities are united in an optimal order.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

Explanation of sample 1

First, we compute the population of cats for each city ($2^{k_ i}$).

4 4 8 8 8

Here, we will show an optimal sequence of cities merging. The cities furthest to the right are merged into a single city with 16 cats:

4 4 8 16

Afterwards, the 4s are merged into a single city with 8 cats:

8 8 16

Afterwards, the 8s are merged into a single city with 16 cats:

16 16

Finally, we can merge the 16s into a singly city with 32 cats:

32

Because there is only a single city left, the answer is 1.

5
2 2 3 3 3

1

4
1 3 3 7

3

12
3 3 3 3 3 4 9 7 7 8 3 3

5