B - 郵便配達と手紙の重み 解説 /

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

配点 : 333 点

問題文

高橋君は郵便局の配達員です。担当する配達エリアには、郵便局を含めて一直線に並ぶ N 個の地点があり、順に地点 1, 地点 2, \ldots, 地点 N と番号が付けられています。隣り合う地点の間の距離はいずれも 1 です。地点 1 に郵便局があります。

各地点 i（2 \leq i \leq N）には B_i 通の手紙を届ける必要があります。郵便局である地点 1 に届ける手紙はありません。

高橋君は手紙を届けるために、以下のような 配達ルート を 0 回以上、好きな回数だけ行うことができます。

  1. 出発： 郵便局（地点 1）から出発する。出発時に、まだ届けていない手紙の中から好きなものを好きな通数だけ選んで持つ。持たないこともできる。1 回のルートで持てる手紙の通数に上限はない。
  2. 往路： 地点 1 から地点番号が増える方向（地点 1 \to 2 \to 3 \to \cdots）へ 1 地点ずつ進む。往路で到達した各地点において、手元に持っているその地点宛ての手紙を好きな通数だけ届けることができる（届けなくてもよい）。手紙はその届け先の地点でのみ届けることができ、異なる地点で届けることはできない。往路の途中、到達したどの地点ででも往路を終了し、帰路に移ることができる（地点 1 で即座に帰路に移ることもできるが、その場合移動が発生しないため疲労度は 0 である）。
  3. 帰路： 往路を終了した地点から郵便局（地点 1）に直接戻る。帰路では疲労度は一切発生しない。また、帰路では手紙を届けることもできない。届けなかった手紙は郵便局に持ち帰り、以降のルートで再び持ち出すことができる。

同じ地点宛ての手紙を複数回のルートに分けて届けることもできます。

1 回のルートにおける 疲労度 は次のように計算されます。往路において地点 p から隣の地点 p+1 へ移動するとき（p \geq 1）、そのときに手元に持っている手紙の通数（持ち出した手紙のうち、まだどの地点にも届けていない手元に残っている手紙の通数）に等しい疲労度が発生します。例えば、地点 1 を出発して地点 2 に向かう移動でも、手元の手紙の通数分の疲労度が発生します。疲労度が発生するのは往路の移動時のみです。1 回のルートの疲労度は、そのルートの往路における全ての移動で発生した疲労度の合計です。

全ての手紙を届けるために必要な、全ルートの疲労度の合計の最小値を求めてください。

制約

  • 2 \leq N \leq 10^6
  • 0 \leq B_i \leq 10^7（2 \leq i \leq N）
  • 入力は全て整数である
  • この制約のもとで、答えは符号付き 64bit 整数に収まる

入力

N
B_2 B_3 \ldots B_N
  • 1 行目には、地点の数を表す整数 N が与えられる。
  • 2 行目には、地点 2 から地点 N それぞれに届ける手紙の通数 B_2, B_3, \ldots, B_N が、スペース区切りで与えられる。

出力

全ての手紙を届けるために必要な疲労度合計の最小値を 1 行で出力せよ。

入力例 1

4
2 1 3

出力例 1

13

入力例 2

5
0 4 0 2

出力例 2

16

入力例 3

12
5 0 8 3 12 1 0 7 4 10 6

出力例 3

365

入力例 4

30
100 250 0 75 320 18 999 40 0 560 123 456 789 10 2048 37 81 600 5 900 333 0 712 64 128 1024 16 450 777

出力例 4

184621

入力例 5

2
10000000

出力例 5

10000000

Score : 333 pts

Problem Statement

Takahashi is a mail carrier. In his delivery area, there are N points arranged in a straight line, including the post office, numbered 1, 2, \ldots, N in order. The distance between any two adjacent points is 1. Point 1 contains the post office.

For each point i (2 \leq i \leq N), B_i letters must be delivered. No letters need to be delivered to point 1 (the post office).

To deliver the letters, Takahashi can perform the following delivery route 0 or more times, as many times as he likes:

  1. Departure: Start at the post office (point 1). Upon departure, choose any number of undelivered letters to carry. He may choose to carry none. There is no limit to the number of letters he can carry in a single route.
  2. Outbound Journey: Move 1 point at a time from point 1 in the direction of increasing point numbers (point 1 \to 2 \to 3 \to \cdots). At each point reached during the outbound journey, he can deliver any number of letters currently in his possession that are addressed to that point (he may also choose not to deliver any). Letters can only be delivered to their designated destination point, not to any other points. He can end the outbound journey and transition to the return journey at any point he has reached (he can even transition to the return journey immediately at point 1, in which case no movement occurs and the fatigue incurred is 0).
  3. Return Journey: Return directly to the post office (point 1) from the point where the outbound journey ended. No fatigue is incurred during the return journey. Additionally, no letters can be delivered during the return journey. Undelivered letters are brought back to the post office and can be carried again in subsequent routes.

Letters addressed to the same point can be delivered across multiple different routes.

The fatigue incurred in a single route is calculated as follows: When moving from point p to the adjacent point p+1 (p \geq 1) during the outbound journey, fatigue equal to the number of letters currently in his possession (the number of carried letters that have not yet been delivered to any point and remain in his hands) is incurred. For example, even during the movement from point 1 to point 2 upon departure, fatigue equal to the number of letters in his possession is incurred. Fatigue is only incurred during outbound movements. The fatigue of a single route is the sum of the fatigue incurred during all movements in that route's outbound journey.

Find the minimum sum of fatigue across all routes required to deliver all letters.

Constraints

  • 2 \leq N \leq 10^6
  • 0 \leq B_i \leq 10^7 (2 \leq i \leq N)
  • All input values are integers.
  • Under these constraints, the answer fits within a signed 64-bit integer.

Input

N
B_2 B_3 \ldots B_N
  • The first line contains an integer N, representing the number of points.
  • The second line contains the number of letters to be delivered to points 2 through N, B_2, B_3, \ldots, B_N, separated by spaces.

Output

Print the minimum total fatigue required to deliver all letters in a single line.

Sample Input 1

4
2 1 3

Sample Output 1

13

Sample Input 2

5
0 4 0 2

Sample Output 2

16

Sample Input 3

12
5 0 8 3 12 1 0 7 4 10 6

Sample Output 3

365

Sample Input 4

30
100 250 0 75 320 18 999 40 0 560 123 456 789 10 2048 37 81 600 5 900 333 0 712 64 128 1024 16 450 777

Sample Output 4

184621

Sample Input 5

2
10000000

Sample Output 5

10000000