C - Repairing Road Potholes Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君は市の道路管理を担当しています。管理対象の道路は一直線に N 個の区画に分かれており、各区画には路面の高さが定められています。左から i 番目の区画の路面の高さは H_i です。

雨水がたまるのを防ぐため、高橋君は道路の凹んでいる箇所をアスファルトで補修したいと考えています。ここで、区画 i（2 \leq i \leq N - 1）が凹んでいるとは、その区画の路面の高さが左隣と右隣の両方の路面の高さよりも真に小さい状態、すなわち H_{i-1} > H_i かつ H_i < H_{i+1} が成り立つことを指します。両端の区画（区画 1 および区画 N）は凹んでいるとはみなしません。特に、N \leq 2 の場合は凹んでいる区画は存在しません。

高橋君は次の操作を 0 回以上繰り返し行うことができます。

  • 操作： N 個の区画のうち 1 つを選び、その区画の路面の高さを 1 だけ増やす。同じ区画を複数回選んでもよい。路面の高さを減らすことはできない。

なお、ある区画の路面の高さを上げた結果、別の区画が新たに凹みの条件を満たすようになる場合があることに注意してください。

すべての凹んでいる区画をなくすために必要な操作回数の最小値を求めてください。すなわち、どの区画 i（2 \leq i \leq N - 1）についても H_{i-1} > H_i かつ H_i < H_{i+1} が成り立たないようにするための最小操作回数を求めてください。

制約

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

入力

N
H_1 H_2 \ldots H_N
  • 1 行目には、区画の数を表す整数 N が与えられる。
  • 2 行目には、各区画の路面の高さを表す N 個の整数 H_1, H_2, \ldots, H_N がスペース区切りで与えられる。

出力

すべての凹みをなくすために必要な最小の操作回数を 1 行で出力せよ。

入力例 1

5
3 1 4 2 5

出力例 1

4

入力例 2

4
1 2 3 4

出力例 2

0

入力例 3

12
8 3 7 7 2 9 4 4 6 1 5 5

出力例 3

13

入力例 4

40
100 60 80 20 90 90 10 70 30 110 50 120 120 40 130 20 140 60 60 150 30 160 70 170 170 50 180 40 190 80 200 90 90 210 10 220 100 230 60 240

出力例 4

1500

入力例 5

1
1000000000

出力例 5

0

Score : 333 pts

Problem Statement

Takahashi is in charge of road maintenance for the city. The road under his management is divided into N sections in a straight line, and each section has a specified road surface height. The height of the i-th section from the left is H_i.

To prevent rainwater from pooling, Takahashi wants to repair the depressed parts of the road with asphalt. Here, section i (2 \leq i \leq N - 1) is said to be depressed if the height of its road surface is strictly smaller than the heights of both its left and right neighbors, i.e., H_{i-1} > H_i and H_i < H_{i+1} hold. The sections at both ends (section 1 and section N) are never considered depressed. In particular, if N \leq 2, there are no depressed sections.

Takahashi can perform the following operation zero or more times:

  • Operation: Choose one of the N sections and increase its road surface height by 1. The same section can be chosen multiple times. The road surface height cannot be decreased.

Note that increasing the height of a section may cause another section to newly satisfy the condition of being depressed.

Find the minimum number of operations required to eliminate all depressed sections. That is, find the minimum number of operations to ensure that for every section i (2 \leq i \leq N - 1), the condition H_{i-1} > H_i and H_i < H_{i+1} does not hold.

Constraints

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

Input

N
H_1 H_2 \ldots H_N
  • The first line contains an integer N, representing the number of sections.
  • The second line contains N space-separated integers H_1, H_2, \ldots, H_N, representing the road surface heights of the sections.

Output

Print the minimum number of operations required to eliminate all depressions in a single line.

Sample Input 1

5
3 1 4 2 5

Sample Output 1

4

Sample Input 2

4
1 2 3 4

Sample Output 2

0

Sample Input 3

12
8 3 7 7 2 9 4 4 6 1 5 5

Sample Output 3

13

Sample Input 4

40
100 60 80 20 90 90 10 70 30 110 50 120 120 40 130 20 140 60 60 150 30 160 70 170 170 50 180 40 190 80 200 90 90 210 10 220 100 230 60 240

Sample Output 4

1500

Sample Input 5

1
1000000000

Sample Output 5

0