A - Steep Stairs Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は、N 段の階段を 1 段目、2 段目、\ldots、N 段目の順に、地面から出発して登ります。i 段目に上がるときの段差の高さ（直前の位置との高低差）は A_i です。

高橋君は体力を消耗しながら階段を登ります。各段における体力の消耗量は次のように決まります。

  • 1 段目に上がるとき（地面から 1 段目へ上がるとき）は、それ以前に上がった段差がないため余計な負担は発生せず、段差の高さに等しい A_1 の体力を消耗します。
  • i \geq 2 のとき、i 段目に上がるときの段差の高さ A_i が、i-1 段目に上がったときの段差の高さ A_{i-1} より真に大きい場合（すなわち A_i > A_{i-1} のとき）、急に段差が大きくなったことで足に余計な負担がかかり、通常の 2 倍である 2 \times A_i の体力を消耗します。
  • i \geq 2 のとき、A_i \leq A_{i-1} ならば余計な負担はかからず、A_i の体力を消耗します。

高橋君が N 段すべてを登り終えたとき、消耗した体力の合計を求めてください。

制約

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

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、階段の段数を表す整数 N が与えられる。
  • 2 行目には、i 段目に上がるときの段差の高さを表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

高橋君が消耗する体力の合計を 1 行で出力せよ。

入力例 1

5
3 2 4 1 5

出力例 1

24

入力例 2

1
1000000000

出力例 2

1000000000

入力例 3

10
1 2 3 4 5 6 7 8 9 10

出力例 3

109

Score : 233 pts

Problem Statement

Takahashi climbs an N-step staircase, ascending steps 1, 2, \ldots, N in order, starting from the ground. The height of the step (the difference in elevation from his immediately previous position) when climbing to step i is A_i.

Takahashi consumes stamina as he climbs the stairs. The stamina consumed at each step is determined as follows:

  • When climbing to step 1 (from the ground to step 1), there is no previous step, so no extra burden is incurred, and he consumes stamina equal to the step height, which is A_1.
  • For i \geq 2, if the step height A_i when climbing to step i is strictly greater than the step height A_{i-1} when climbing to step i-1 (i.e., A_i > A_{i-1}), the sudden increase in step height places extra burden on his legs, and he consumes 2 \times A_i stamina, which is twice the normal amount.
  • For i \geq 2, if A_i \leq A_{i-1}, no extra burden is incurred, and he consumes A_i stamina.

Find the total stamina consumed when Takahashi finishes climbing all N steps.

Constraints

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

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of steps.
  • The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, where A_i represents the step height when climbing to step i.

Output

Print the total stamina consumed by Takahashi on a single line.

Sample Input 1

5
3 2 4 1 5

Sample Output 1

24

Sample Input 2

1
1000000000

Sample Output 2

1000000000

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10

Sample Output 3

109