分数: 250 点
问题陈述
你有一个空序列并且 N 球。尺寸 i第一个球 (1 \leq i \leq N) is 2^{A_i}.
您将执行 N 操作。
在 i-第操作,您添加 i-第一个球到序列的右端,并重复以下步骤:
- 如果序列中有一个或更少的球,则结束操作。
- 如果序列中最右边的球和第二个最右边的球有 不同 尺寸,结束操作。
- 如果序列中最右边的球和第二个最右边的球有 相同 大小,删除这两个球,并在序列的右端添加一个新球,其大小等于两个删除球的大小之和。然后,返回步骤 1 并重复该过程。
确定序列中剩余的球数 N 操作。
约束
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印序列中球的数量 N 操作。
示例输入 1
7 2 1 1 3 5 3 3
示例输出 1
3
操作过程如下:
- 第一次操作后,序列有一个球,尺寸为 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
5 0 0 0 1 2
示例输出 2
4
操作过程如下:
- 第一次操作后,序列有一个球,尺寸为 2^0.
- 第二次操作后,序列有一个球,尺寸为 2^1.
- 第三次操作后,序列有两个球,尺寸为 2^1 和 2^0 按顺序。
- 第四次操作后,序列有三个球,尺寸为 2^1, 2^0, 2^1 按顺序。
- 第五次操作后,序列有四个球,尺寸为 2^1, 2^0, 2^1, 2^2 按顺序。
因此,您应该打印 4,序列中的最终球数。