← 返回题目列表

AtCoder · abc351_c

E. 合并球

中文机器翻译题面 查看原题

分数: 250 点

问题陈述

你有一个空序列并且 N 球。尺寸 i第一个球 (1 \leq i \leq N) is 2^{A_i}.

您将执行 N 操作。
在 i-第操作,您添加 i-第一个球到序列的右端,并重复以下步骤:

  1. 如果序列中有一个或更少的球,则结束操作。
  2. 如果序列中最右边的球和第二个最右边的球有 不同 尺寸,结束操作。
  3. 如果序列中最右边的球和第二个最右边的球有 相同 大小,删除这两个球,并在序列的右端添加一个新球,其大小等于两个删除球的大小之和。然后,返回步骤 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,序列中的最终球数。