4195: Merge the balls

# Merge the balls ### 内存 1024MB ### 时间 2S ## 题目描述 有一个空序列和 $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 ``` 7 2 1 1 3 5 3 3 ``` ### 输出样例1 ``` 3 ``` ### 输入样例2 ``` 5 0 0 0 1 2 ``` ### 输出样例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 \leq N \leq 2 \times 10^5$ $0 \leq A_i \leq 10^9$ 所有输入值都是整数。 ## 题目来源 ABC351C