B - Piano Practice Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君はピアニストを目指しており、今日は N 曲の練習曲を 1 番目から N 番目まで順番に演奏することにしました。

i 番目の曲には整数の難易度 D_i が設定されています。各曲の演奏にかかる時間は以下のルールで決まります。

  • 1 番目の曲の演奏には D_1 分かかります。
  • 2 番目以降の曲（2 \leq i \leq N）については、直前に演奏した曲との難易度の関係によって演奏時間が変わります。
  • 直前の曲より難易度が真に大きい場合（D_{i-1} < D_i）、前の曲の演奏でウォーミングアップができているため、かかる時間は \lfloor D_i / 2 \rfloor 分に短縮されます。ここで \lfloor x \rfloor は x を超えない最大の整数を表します（すなわち、D_i を 2 で割って小数点以下を切り捨てた値です）。
  • 直前の曲の難易度以下である場合（D_{i-1} \geq D_i）、短縮は適用されず D_i 分かかります。

高橋君がすべての曲を 1 番目から N 番目まで順番に演奏するとき、合計でかかる時間は何分でしょうか。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D_i \leq 10^9
  • 入力はすべて整数

入力

N
D_1 D_2 \ldots D_N
  • 1 行目には、曲の数を表す整数 N が与えられる。
  • 2 行目には、各曲の難易度を表す N 個の整数 D_1, D_2, \ldots, D_N がスペース区切りで与えられる。

出力

高橋君がすべての曲を演奏するのにかかる合計時間（分）を 1 行に出力せよ。

入力例 1

5
3 5 4 8 10

出力例 1

18

入力例 2

7
1 2 3 4 5 6 7

出力例 2

13

入力例 3

10
100 50 200 200 300 150 400 500 600 100

出力例 3

1600

Score : 233 pts

Problem Statement

Takahashi aspires to become a pianist, and today he has decided to play N practice pieces in order from the 1-st to the N-th.

The i-th piece has an integer difficulty D_i. The time required to perform each piece is determined by the following rules:

  • The 1-st piece takes D_1 minutes to perform.
  • For the 2-nd piece onward (2 \leq i \leq N), the performance time depends on the relationship between the difficulty of the current piece and the immediately preceding piece.
  • If the difficulty is strictly greater than the previous piece (D_{i-1} < D_i), then the previous piece served as a warm-up, so the time is reduced to \lfloor D_i / 2 \rfloor minutes. Here, \lfloor x \rfloor denotes the largest integer not exceeding x (that is, the value obtained by dividing D_i by 2 and rounding down).
  • If the difficulty is less than or equal to the previous piece (D_{i-1} \geq D_i), no reduction is applied and the piece takes D_i minutes.

When Takahashi performs all pieces in order from the 1-st to the N-th, how many minutes does it take in total?

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq D_i \leq 10^9
  • All inputs are integers.

Input

N
D_1 D_2 \ldots D_N
  • The first line contains an integer N representing the number of pieces.
  • The second line contains N integers D_1, D_2, \ldots, D_N separated by spaces, representing the difficulty of each piece.

Output

Print in one line the total time (in minutes) it takes for Takahashi to perform all the pieces.

Sample Input 1

5
3 5 4 8 10

Sample Output 1

18

Sample Input 2

7
1 2 3 4 5 6 7

Sample Output 2

13

Sample Input 3

10
100 50 200 200 300 150 400 500 600 100

Sample Output 3

1600