103512: [Atcoder]ABC351 C - Merge the balls

Problem Statement

You have an empty sequence and $N$ balls. The size of the $i$-th ball $(1 \leq i \leq N)$ is $2^{A_i}$.

You will perform $N$ operations.
In the $i$-th operation, you add the $i$-th ball to the right end of the sequence, and repeat the following steps:

1. If the sequence has one or fewer balls, end the operation.
2. If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
3. If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.

Determine the number of balls remaining in the sequence after the $N$ operations.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

Output

Print the number of balls in the sequence after the $N$ operations.

Sample Input 1

7
2 1 1 3 5 3 3

Sample Output 1

3

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size $2^2$.
• After the second operation, the sequence has two balls, of sizes $2^2$ and $2^1$ in order.
• After the third operation, the sequence has one ball, of size $2^3$. This is obtained as follows:
  • When the third ball is added during the third operation, the sequence has balls of sizes $2^2, 2^1, 2^1$ in order.
  • The first and second balls from the right have the same size, so these balls are removed, and a ball of size $2^1 + 2^1 = 2^2$ is added. Now, the sequence has balls of sizes $2^2, 2^2$.
  • Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size $2^2 + 2^2 = 2^3$ is added, leaving the sequence with a ball of size $2^3$.
• After the fourth operation, the sequence has one ball, of size $2^4$.
• After the fifth operation, the sequence has two balls, of sizes $2^4$ and $2^5$ in order.
• After the sixth operation, the sequence has three balls, of sizes $2^4$, $2^5$, $2^3$ in order.
• After the seventh operation, the sequence has three balls, of sizes $2^4$, $2^5$, $2^4$ in order.

Therefore, you should print $3$, the final number of balls in the sequence.

Sample Input 2

5
0 0 0 1 2

Sample Output 2

4

The operations proceed as follows:

• After the first operation, the sequence has one ball, of size $2^0$.
• After the second operation, the sequence has one ball, of size $2^1$.
• After the third operation, the sequence has two balls, of sizes $2^1$ and $2^0$ in order.
• After the fourth operation, the sequence has three balls, of sizes $2^1$, $2^0$, $2^1$ in order.
• After the fifth operation, the sequence has four balls, of sizes $2^1$, $2^0$, $2^1$, $2^2$ in order.

Therefore, you should print $4$, the final number of balls in the sequence.

问题描述

你有一个空序列和 $N$ 个球。第 $i$ 个球（$1 \leq i \leq N$）的大小为 $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

操作过程如下：

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

操作过程如下：

• 第一次操作后，序列中有1个球，大小为 $2^0$。
• 第二次操作后，序列中有1个球，大小为 $2^1$。
• 第三次操作后，序列中有两个球，按顺序大小分别为 $2^1$ 和 $2^0$。
• 第四次操作后，序列中有三个球，按顺序大小分别为 $2^1$、$2^0$、$2^1$。
• 第五次操作后，序列中有四个球，按顺序大小分别为 $2^1$、$2^0$、$2^1$、$2^2$。

因此，你应该打印出 $4$，即序列中最终剩余的球的数量。