[ABC351C] Merge the balls

#### 问题陈述 你有一个空序列和 $N$ 个球。第 $i$ 球 $(1 \leq i \leq N)$ 的大小是 $2^{A_i}$ 。 您将执行 $N$ 次操作。 在第 $i$ 操作中，你将第 $i$ 球添加到序列的右端，然后重复下面的步骤： 1. 如果序列中只有一个或更少的球，则结束操作。 2. 如果序列中最右边的球和第二个最右边的球大小不同，结束操作。 3. 如果序列中最右边的球和最右边的第二个球大小相同，则移除这两个球，并在序列右端添加一个新球，其大小等于移除的两个球的大小之和。然后回到步骤 $1$，重复上述过程。 确定 $N$ 次操作后序列中剩余的球数。

[problemUrl]: https://atcoder.jp/contests/abc351/tasks/abc351_c 空の列と、$ N $ 個のボールがあります。$ i $ 個目 $ (1\leq\ i\leq\ N) $ のボールの大きさは $ 2^{A_i} $ です。 これから $ N $ 回の操作を行います。 $ i $ 回目の操作では、$ i $ 個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。 1. 列にあるボールが $ 1 $ つ以下ならば操作を終了する。 2. 列にあるボールのうち右から $ 1 $ 番目のものと $ 2 $ 番目のものの大きさが **異なる** ならば操作を終了する。 3. 列にあるボールのうち右から $ 1 $ 番目のものと $ 2 $ 番目のものの大きさが **等しい** ならば、$ 2 $ つのボールを取り除き、「取り除かれた $ 2 $ つのボールの大きさの和」の大きさのボール $ 1 $ つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。 $ N $ 回の操作の後で、列にあるボールの数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

$ N $ 回の操作の後で、列にあるボールの数を出力せよ。

7
2 1 1 3 5 3 3

3

5
0 0 0 1 2

4

### 制約 - $ 1\leq\ N\ \leq\ 2\times\ 10^5 $ - $ 0\leq\ A_i\leq\ 10^9 $ - 入力はすべて整数 ### Sample Explanation 1 操作は次のように行われます。 - $ 1 $ 回目の操作の後、列にあるボールは $ 1 $ つで、大きさは $ 2^2 $ です。 - $ 2 $ 回目の操作の後、列にあるボールは $ 2 $ つで、大きさは順に $ 2^2 $, $ 2^1 $ です。 - $ 3 $ 回目の操作の後、列にあるボールは $ 1 $ つで、大きさは $ 2^3 $ です。これは次のようにして得ることができます。 - $ 3 $ 回目の操作において $ 3 $ 個目のボールを付け加えたとき、列にあるボールの大きさは順に $ 2^2,2^1,2^1 $ となります。 - 右から $ 1 $ 番目のボールと $ 2 $ 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが $ 2^1+2^1=2^2 $ のボールが追加されます。このとき、列にあるボールの大きさは $ 2^2 $, $ 2^2 $ となります。 - さらに、再び右から $ 1 $ 番目のボールと $ 2 $ 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが $ 2^2+2^2=2^3 $ のボールが追加され、列にあるボールの大きさは $ 2^3 $ となります。 - $ 4 $ 回目の操作の後、列にあるボールは $ 1 $ つで、大きさは $ 2^4 $ です。 - $ 5 $ 回目の操作の後、列にあるボールは $ 2 $ つで、大きさは順に $ 2^4 $, $ 2^5 $ です。 - $ 6 $ 回目の操作の後、列にあるボールは $ 3 $ つで、大きさは順に $ 2^4 $, $ 2^5 $, $ 2^3 $ です。 - $ 7 $ 回目の操作の後、列にあるボールは $ 3 $ つで、大きさは順に $ 2^4 $, $ 2^5 $, $ 2^4 $ です。 よって、最後に列にあるボールの数である $ 3 $ を出力します。 ### Sample Explanation 2 操作は次のように行われます。 - $ 1 $ 回目の操作の後、列にあるボールは $ 1 $ つで、大きさは $ 2^0 $ です。 - $ 2 $ 回目の操作の後、列にあるボールは $ 1 $ つで、大きさは $ 2^1 $ です。 - $ 3 $ 回目の操作の後、列にあるボールは $ 2 $ つで、大きさは順に $ 2^1 $, $ 2^0 $ です。 - $ 4 $ 回目の操作の後、列にあるボールは $ 3 $ つで、大きさは順に $ 2^1 $, $ 2^0 $, $ 2^1 $ です。 - $ 5 $ 回目の操作の後、列にあるボールは $ 4 $ つで、大きさは順に $ 2^1 $, $ 2^0 $, $ 2^1 $, $ 2^2 $ です。 よって、最後に列にあるボールの数である $ 4 $ を出力します。