合并球

题目描述

你有一个空序列和 $N$ 个球。第 $i$ 个球 $(1 \leq i \leq N)$ 的大小为 $2^{A_i}$。

你将执行 $N$ 次操作。

在第 $i$ 次操作中,你先把第 $i$ 个球加到序列的右端,然后重复以下步骤:

1. 如果序列中的球数为 1 个或更少,结束本次操作。
2. 如果序列右端第一个球和第二个球的大小不同,结束本次操作。
3. 如果序列右端第一个球和第二个球的大小相同,移除这两个球,并在序列右端加入一个大小等于被移除两球大小之和的新球。然后回到步骤 1,重复该过程。

求 $N$ 次操作结束后序列中剩余的球数。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出 $N$ 次操作结束后序列中剩余的球数。

样例

7
2 1 1 3 5 3 3

3

操作过程如下:

第一次操作结束后,序列中有 1 个球,大小为 $2^2$。

第二次操作结束后,序列中有 2 个球,大小依次为 $2^2$ 和 $2^1$。

第三次操作结束后,序列中有 1 个球,大小为 $2^3$。其过程如下:

第三次操作加入第三个球时,序列中的球大小依次为 $2^2, 2^1, 2^1$。

从右数第一个和第二个球大小相同,因此移除这两个球,并加入一个大小为 $2^1 + 2^1 = 2^2$ 的球。此时序列中的球大小依次为 $2^2, 2^2$。

再次地,从右数第一个和第二个球大小相同,因此移除这两个球,并加入一个大小为 $2^2 + 2^2 = 2^3$ 的球,序列中剩下大小为 $2^3$ 的一个球。

第四次操作结束后,序列中有 1 个球,大小为 $2^4$。

第五次操作结束后,序列中有 2 个球,大小依次为 $2^4$ 和 $2^5$。

第六次操作结束后,序列中有 3 个球,大小依次为 $2^4$, $2^5$, $2^3$。

第七次操作结束后,序列中有 3 个球,大小依次为 $2^4$, $2^5$, $2^4$。

因此,最终序列中的球数为 3,输出 3。

5
0 0 0 1 2

4

操作过程如下:

第一次操作结束后,序列中有 1 个球,大小为 $2^0$。

第二次操作结束后,序列中有 1 个球,大小为 $2^1$。

第三次操作结束后,序列中有 2 个球,大小依次为 $2^1$ 和 $2^0$。

第四次操作结束后,序列中有 3 个球,大小依次为 $2^1$, $2^0$, $2^1$。

第五次操作结束后,序列中有 4 个球,大小依次为 $2^1$, $2^0$, $2^1$, $2^2$。

因此,最终序列中的球数为 4,输出 4。

数据范围

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$
• 输入中的所有值均为整数。