题目描述

Gattekatt 这个国家形状非常奇特，极其狭长，这导致它的 $N$ 个城市各自占据了国家的一段区间。 这些城市从左到右依次编号为 1 到 $N$。每个城市都有一群猫。有趣的是，猫的数量总是 $2$ 的正整数幂。 （Gattekatt 有很多很多猫）。

为了让国家为潜在的老鼠入侵做好准备，大家希望尽可能多的城市能够联合起来。 不幸的是，这些城市对于愿意和谁合作非常挑剔。对于两个城市 $a$ 和 $b$ 来说，要合并必须满足以下条件：

• 城市 $a$ 和城市 $b$ 是相邻的。
• 城市 $a$ 和城市 $b$ 的猫的数量完全相同。这是因为城市的猫数量与该城市的政治影响力直接相关，一个城市不会考虑与它认为政治影响力较低的城市合作。

当两个相邻的城市 $a$ 和 $b$（每个城市都有 $2^k$ 只猫）决定合并时，它们会形成一个拥有 $2^{k+1}$ 只猫的新城市。 这个新城市可以继续与原城市 $a$ 左边的城市或原城市 $b$ 右边的城市进行合并。

Gattekatt 的居民们现在希望你帮助计算，如果以最优的顺序进行合并，最终可以剩下的最少城市数量是多少。

输入格式

输入的第一行包含一个整数 $N$（$1 \leq N \leq 10^6$）。

输入的第二行包含 $N$ 个整数 $k_1, k_2, \dots, k_N$ ($0 \leq k_i \leq 10^9$)。 每个 $k_i$ 表示第 $i$ 个城市有 $2^{k_i}$ 只猫作为居民。

输出格式

输出一个整数：如果城市以最优顺序合并，最终可以剩下的最少城市数量。

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

提示

样例 1 解释

首先，我们计算每个城市的猫的数量（$2^{k_i}$）。

4 4 8 8 8

这里，我们展示一个最优的城市合并序列。 最右边的两个城市合并成一个拥有 16 只猫的城市：

4 4 8 16

之后，两个 4 合并成一个拥有 8 只猫的城市：

8 8 16

之后，两个 8 合并成一个拥有 16 只猫的城市：

16 16

最后，我们可以将两个 16 合并成一个拥有 32 只猫的城市：

32

因为最后只剩下一个城市，所以答案是 1。

子任务

本题采用捆绑测试。 | 子任务编号 | 得分 | 限制 | |:-:|:-:|---| | $1$ | $7$| $N \leq 10, k_i \leq 30$ | | $2$ | $14$ | $N \leq 200, k_i \leq 30$ | | $3$ | $15$ | $N \leq 2000, k_i \leq 30$ | | $4$ | $9$| $N \leq 2000$ | | $5$ | $37$ | $k_i \leq 30$ | | $6$ | $18$ | 无额外约束。 |