Score: $250$ points

问题陈述

你有一段空序列和 $N$ 个球。第 $i$ 个球的大小 $(1 \leq i \leq N)$ 是 $2^{A_i}$。

你将执行 $N$ 次操作。 在第 $i$ 次操作中，你将第 $i$ 个球添加到序列的右端，然后重复以下步骤：

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

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

以上为大语言模型 kimi 翻译，仅供参考。

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.