Merge the balls

题目描述

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

如果序列中有一个或更少的球，则结束该次操作。 如果序列中最右边的球和次右边的球的大小不同，则结束该次操作。 如果序列中最右边的球和次右边的球的大小相同，则移除这两个球，并在序列最右端加入一个新球，其大小等于被移除的两个球大小之和。然后，返回步骤 1 并重复该过程。

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

输入格式

输入按下述格式从标准输入给出： $N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

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

7
2 1 1 3 5 3 3

3

5
0 0 0 1 2

4

提示

$1 \leq N \leq 2 \times 10^5$ $0 \leq A_i \leq 10^9$ 所有输入值均为整数。操作过程如下：

在第一次操作之后，序列有一个球，大小为 $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^0$。 在第二次操作之后，序列有一个球，大小为 $2^1$。 在第三次操作之后，序列有两个球，按顺序分别为 $2^1$ 和 $2^0$。 在第四次操作之后，序列有三个球，按顺序分别为 $2^1$、$2^0$、$2^1$。 在第五次操作之后，序列有四个球，按顺序分别为 $2^1$、$2^0$、$2^1$、$2^2$。

因此，你应该输出 $4$，作为最终剩余的球的数量。

标签: AtCoder|abc351C

来源

AtCoder|abc351C