A - カードバトル 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 266 点

問題文

高橋君はカードゲームで遊んでいます。

テーブルの上に N 枚のカードが一列に並べられています。左から i 番目のカードを「カード i」と呼び、カード i には攻撃力 A_i が書かれています。

高橋君は、i = 1, 2, \ldots, N-1 の順に、各 i についてちょうど一度ずつ以下の処理を行います。ここで処理の対象は、テーブル上で物理的に隣接しているカードではなく、番号が i と i+1 であるカードのペアです。カードの番号はテーブルから取り除かれた後も変わりません。

  • カード i とカード i+1 のうち少なくとも一方がすでにテーブルから取り除かれている場合は、何もしない。
  • カード i とカード i+1 がともにテーブルに残っている場合、両者のその時点での攻撃力を比較する。
  • 攻撃力が等しい場合は、何もしない。
  • 攻撃力が異なる場合は、攻撃力が大きい方のカードがもう一方を吸収する。具体的には、攻撃力 X のカードが攻撃力 Y（X > Y）のカードを吸収すると、次のことが起こる。
  • 吸収された側（攻撃力 Y）のカードはテーブルから取り除かれ、以降の処理ではテーブルに残っていないものとして扱われる。
  • 吸収した側のカードはそのままの番号でテーブルに残り、攻撃力が X + \lfloor Y / 2 \rfloor に更新される。ここで \lfloor \cdot \rfloor は床関数（小数点以下切り捨て）を表す。この更新された攻撃力が、以降の処理で用いられる。

なお、カードの攻撃力は吸収によって変化しうるため、各処理の時点での最新の攻撃力が比較に用いられることに注意してください。

i = N-1 までの処理がすべて終了した後、テーブルに残っているカードの枚数を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数である。

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、カードの枚数を表す整数 N が与えられる。
  • 2 行目には、各カードの攻撃力を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

すべての処理が終了した後にテーブルに残っているカードの枚数を 1 行で出力せよ。

入力例 1

5
3 1 4 1 5

出力例 1

3

入力例 2

4
2 2 2 2

出力例 2

4

入力例 3

10
5 3 8 6 2 7 1 9 4 10

出力例 3

5

入力例 4

20
100 37 85 12 99 44 67 23 78 56 91 33 72 15 88 41 63 29 50 1000000000

出力例 4

10

入力例 5

1
1

出力例 5

1

Score : 266 pts

Problem Statement

Takahashi is playing a card game.

N cards are arranged in a row on the table. The i-th card from the left is called "card i", and card i has an attack power of A_i written on it.

Takahashi performs the following operation exactly once for each i, in the order i = 1, 2, \ldots, N-1. Note that the operation targets the pair of cards with numbers i and i+1, not cards that are physically adjacent on the table. A card's number does not change even after it is removed from the table.

  • If at least one of card i and card i+1 has already been removed from the table, do nothing.
  • If both card i and card i+1 remain on the table, compare their current attack powers.
  • If their attack powers are equal, do nothing.
  • If their attack powers differ, the card with the higher attack power absorbs the other. Specifically, when a card with attack power X absorbs a card with attack power Y (X > Y), the following occurs:
  • The absorbed card (with attack power Y) is removed from the table and is treated as no longer on the table in subsequent operations.
  • The absorbing card remains on the table with the same number, and its attack power is updated to X + \lfloor Y / 2 \rfloor, where \lfloor \cdot \rfloor denotes the floor function (rounding down to the nearest integer). This updated attack power is used in subsequent operations.

Note that since a card's attack power can change through absorption, the latest attack power at the time of each operation is used for comparison.

After all operations up to i = N-1 have been completed, find the number of cards remaining on the table.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of cards.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the attack power of each card.

Output

Print in one line the number of cards remaining on the table after all operations have been completed.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

3

Sample Input 2

4
2 2 2 2

Sample Output 2

4

Sample Input 3

10
5 3 8 6 2 7 1 9 4 10

Sample Output 3

5

Sample Input 4

20
100 37 85 12 99 44 67 23 78 56 91 33 72 15 88 41 63 29 50 1000000000

Sample Output 4

10

Sample Input 5

1
1

Sample Output 5

1