AT_abc351_c [ABC351C] Merge the balls

[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

N/A

### 制約 - $ 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 $ を出力します。