C - Merge the balls Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 250 点

問題文

空の列と、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 回の操作の後で、列にあるボールの数を求めてください。

制約

  • 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 回目の操作の後、列にあるボールは 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 を出力します。

入力例 2

5
0 0 0 1 2

出力例 2

4

操作は次のように行われます。

  • 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 を出力します。

Score: 250 points

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.