Problem A
Politiska spelet

Landet Gattekatt har en väldigt ovanlig form. Det är nämligen väldigt avlångt, vilket resulterar i att dess $N$ städer vardera ockuperar sig ett intervall av landet. Städerna är numrerade från $1$ till $N$, från vänster till höger. Varje stad har ett antal katter som invånare. Lustigt nog är antalet katter alltid lika med $2^ k$ för något heltal $k$ (det finns väldigt många katter i Gattekatt). För att förbereda landet inför en potentiell råttinvasion vill regeringen att så många städer som möjligt ska gå tillsammans. Tyvärr är städerna väldigt kräsna kring vem de kan tänka sig att samarbeta med. För att två städer $a$ och $b$ ska gå ihop krävs följande:

• Städerna $a$ och $b$ ligger bredvid varandra.

• Antalet katter i stad $a$ och $b$ är exakt samma. Detta beror på att antalet katter i staden är direkt korrelerat med stadens politiskt inflytande, och en stad kan inte tänka sig samarbeta med en annan stad som de anser har mindre politiskt inflytande.

När två städer $a$ och $b$ som ligger bredvid varandra, som vardera har $2^ k$ stycken katter går samman, sammansätts de till en enda stad, vars kattbefolkning är $2^{k+1}$. Den nya staden kan sedan eventuellt gå samman med staden som var till vänster om $a$ eller höger om $b$.

Topp-politiker från Gattekatt vill nu ha din hjälp att beräkna det minsta antalet städer som kan finnas kvar i slutet om man slår ihop städer i en optimal ordning.

Indata

Den första raden i indatan innehåller heltalet $N$ ($1 \leq N \leq 10^6$).

Den andra raden i indatan innehåller $N$ heltal $k_1,k_2,\dots ,k_ N$ ($1 \leq k_ i \leq 10^9$). Varje $k_ i$ innebär att stad $i$ har $2^{k_ i}$ stycken katter i sig.

Utdata

Skriv ut ett heltal: minsta antalet städer som kan finnas kvar om städerna sammansätts ihop i en optimal ordning.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring av exempelfall 1

Först beräknar vi kattbefolkningarna ($2^{k_ i}$).

4 4 8 8 8

Här är en möjlig optimal sekvens av att städer slås ihop. Städerna längst till höger slås ihop till en stad med 16 katter:

4 4 8 16

Sedan kan fyrorna slås ihop till en stad med 8 katter:

8 8 16

Sedan kan åttorna slås ihop till en stad med 16 katter:

16 16

Til slut kan de två 16 slås ihop till en stad 32 katter:

32

Eftersom det bara finns en stad kvar blir svaret 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