You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自「Atcoder ABC351C」

题目描述

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

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

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

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

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

输入格式

第一行输入一个正整数 $N$。

第二行输入 $N$ 个整数 $A_1,A_2,\cdots,A_n$。

输出格式

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

样例

7
2 1 1 3 5 3 3

3

5
0 0 0 1 2

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\le N\le 2\times 10^5,0\le A_i \le 10^9$，所有输入值都是整数。