[ABC351] C - Merge the balls

C - Merge the balls

Time Limit: 2 sec / Memory Limit: 1024 MB

分数: 250 分

题面

你有一个空序列和 个小球。第 个小球的大小为 。

你将会执行 次操作。
在第 次操作中，你将把第 个小球添加到序列的末尾，并重复以下步骤：

1. 如果序列只有一个或更少的小球，则结束操作。
2. 如果序列中最右边的小球和倒数第二个小球的大小不同，则结束操作。
3. 如果序列中最右边的小球和倒数第二个小球的大小相同，则移除这两个小球，并在序列的最右边添加一个新的小球，大小等于这两个被移除小球的大小之和。之后，回到步骤 1 并重复这个过程。

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

限制条件

• 所有输入均为整数。

---

输入

从标准输入中以以下格式给出：

输出

输出 次操作后序列中的小球数量。

---

输入样例 1

7
2 1 1 3 5 3 3

输出样例 1

3

操作过程如下：

• 第一次操作后，序列中有一颗大小为 的小球。
• 第二次操作后，序列中有两颗小球，大小分别为 和 。
• 第三次操作后，序列中有一颗大小为 的小球。过程如下：
  • 第三个小球添加后，序列中有大小为 的小球。
  • 最右边的两颗小球大小相同，于是这两颗小球被移除，并添加一颗大小为 的小球。现在，序列中有大小为 的小球。
  • 再次，最右边的两颗小球大小相同，这两颗小球被移除，并添加一颗大小为 的小球，使得序列中有一颗大小为 的小球。
• 第四次操作后，序列中有一颗大小为 的小球。
• 第五次操作后，序列中有两颗小球，大小分别为 和 。
• 第六次操作后，序列中有三颗小球，大小分别为 。
• 第七次操作后，序列中有三颗小球，大小分别为 。

因此，应当输出 ，即序列中最终剩余的小球数。

---

输入样例 2

5
0 0 0 1 2

输出样例 2

4

操作过程如下：

• 第一次操作后，序列中有一颗大小为 的小球。
• 第二次操作后，序列中有一颗大小为 的小球。
• 第三次操作后，序列中有两颗小球，大小分别为 和 。
• 第四次操作后，序列中有三颗小球，大小分别为 。
• 第五次操作后，序列中有四颗小球，大小分别为 。

因此，应当输出 ，即序列中最终剩余的小球数。