题目描述

有一个空序列和 $N$ 个球。第 $i$ 个球 ($1 ≤ i ≤ N$) 的大小是 $2^{A_i}$。你将执行 $N$ 次操作：在第 $i$ 次操作中，你将第 $i$ 个球添加到序列的右端，然后重复以下步骤：

1. 如果序列中只有一个或没有球，结束操作。

2. 如果序列中最右边的球和倒数第二个球的大小不同，结束操作。

3. 如果序列中最右边的球和倒数第二个球的大小相同，移除这两个球并在序列右端添加一个新球，新球的大小等于被移除的两个球大小之和。然后，返回步骤$1$并重复此过程。

确定 $N$ 次操作后序列中剩余的球的数量。

输入格式

输入以以下格式从标准输入中给出：
$N$
$A_1$ $A_2$ $\cdots$ $A_N$

输出格式

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

样例

1
2
7
2 1 1 3 5 3 3

1
3

1
2
5
0 0 0 1 2

1
4

样例解释

【样例1说明】
操作过程如下：

• 第一次操作后，序列有一个大小为 $2^2$ 的球。

• 第二次操作后，序列有两个球，大小分别为 $2^2$ 和 $2^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$ 的球。

• 第四次操作后，序列有一个大小为 $2^4$ 的球。

• 第五次操作后，序列有两个球，大小分别为 $2^4$ 和 $2^5$。

• 第六次操作后，序列有三个球，大小分别为 $2^4$、$2^5$、$2^3$。

• 第七次操作后，序列有三个球，大小分别为 $2^4$、$2^5$、$2^4$。

因此，你应该输出 3，这是序列中最终的球的数量。

【样例2说明】
操作过程如下：

• 第一次操作后，序列有一个大小为 $2^0$ 的球。
• 第二次操作后，序列有一个大小为 $2^1$ 的球。
• 第三次操作后，序列有两个球，大小分别为 $2^1$ 和 $2^0$。
• 第四次操作后，序列有三个球，大小分别为 $2^1$、$2^0$、$2^1$。
• 第五次操作后，序列有四个球，大小分别为 $2^1$、$2^0$、$2^1$、$2^2$。

因此，你应该输出 4，这是序列中最终的球的数量。

数据范围

$1 \leq N \leq 2 \times 10^5$
$0 \leq A_i \leq 10^9$
所有输入值都是整数。

来源

• AtCoder ABC351C