E - 山型整地 解説 /

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

配点 : 433 点

問題文

高橋君は N 個の区画からなる土地を管理しています。i 番目の区画の地面の高さは H_i です。

高橋君は、この土地を整地するために次の操作を繰り返し行えます。

操作： 1 \le l \le r \le N を満たす整数の組 (l, r) を一つ選び、l 番目から r 番目までの各区画の高さをそれぞれ 1 だけ減らす。

この操作は 0 回以上何度でも行うことができ、毎回選ぶ (l, r) は自由に決めてよいです（同じ組を複数回選ぶこともできます）。なお、この操作では高さを減らすことのみが可能であり、高さを増やすことはできません。

また、操作の過程および最終状態を含むすべての時点において、すべての区画の高さは 0 以上でなければなりません。

高橋君の目標は、すべての操作が完了した後の土地の高さの列を「山型」にすることです。操作後の i 番目の区画の高さを H'_i とするとき、列 H'_1, H'_2, \ldots, H'_N が山型であるとは、ある添字 k（ 1 \le k \le N ）が存在して、

H'_1 \le H'_2 \le \cdots \le H'_k \ge H'_{k+1} \ge \cdots \ge H'_N

を満たすことをいいます。すなわち、ある k が存在して、H'_1 から H'_k までが広義単調非減少であり、かつ H'_k から H'_N までが広義単調非増加であることを意味します。特に、広義単調非減少な列（k = N の場合）や広義単調非増加な列（k = 1 の場合）、すべての高さが等しい列も山型に含まれます。また、N = 1 のときは常に山型です。

高橋君は操作回数を最小にしつつ土地を山型にしたいと考えています。必要な操作の最小回数を求めてください。

制約

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

入力

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

出力

土地を山型にするために必要な操作の最小回数を 1 行で出力せよ。

入力例 1

5
2 1 3 2 1

出力例 1

1

入力例 2

6
0 2 2 5 3 1

出力例 2

0

入力例 3

15
4 8 1 7 7 3 10 6 2 9 5 5 1 4 0

出力例 3

21

入力例 4

50
12 0 15 15 3 22 7 30 18 5 5 40 1 26 26 9 33 14 14 2 45 11 29 6 6 38 20 4 31 31 8 17 23 23 10 36 13 27 0 19 19 34 16 16 28 21 21 35 24 12

出力例 4

343

入力例 5

1
1000000000

出力例 5

0

Score : 433 pts

Problem Statement

Takahashi manages a piece of land consisting of N plots. The height of the i-th plot is H_i.

To level this land, Takahashi can repeatedly perform the following operation:

Operation: Choose a pair of integers (l, r) satisfying 1 \le l \le r \le N, and decrease the height of each plot from the l-th to the r-th plot by 1.

This operation can be performed zero or more times, and he can freely choose (l, r) each time (the same pair can be chosen multiple times). Note that this operation can only decrease heights; it cannot increase them.

Furthermore, at all points in time, including during the process and in the final state, the height of every plot must be at least 0.

Takahashi's goal is to make the sequence of heights "mountain-shaped" after all operations are completed. Letting H'_i be the height of the i-th plot after the operations, the sequence H'_1, H'_2, \ldots, H'_N is said to be mountain-shaped if there exists an index k (1 \le k \le N) such that:

H'_1 \le H'_2 \le \cdots \le H'_k \ge H'_{k+1} \ge \cdots \ge H'_N

That is, there exists some k such that the sequence from H'_1 to H'_k is monotonically non-decreasing, and the sequence from H'_k to H'_N is monotonically non-increasing. In particular, a monotonically non-decreasing sequence (the case where k = N), a monotonically non-increasing sequence (the case where k = 1), and a sequence where all heights are equal are also considered mountain-shaped. Additionally, when N = 1, the sequence is always mountain-shaped.

Takahashi wants to make the land mountain-shaped while minimizing the number of operations. Find the minimum number of operations required.

Constraints

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

Input

N
H_1 H_2 \cdots H_N
  • The first line contains an integer N, representing the number of plots.
  • The second line contains N space-separated integers H_1, H_2, \ldots, H_N, representing the height of each plot.

Output

Print the minimum number of operations required to make the land mountain-shaped in a single line.

Sample Input 1

5
2 1 3 2 1

Sample Output 1

1

Sample Input 2

6
0 2 2 5 3 1

Sample Output 2

0

Sample Input 3

15
4 8 1 7 7 3 10 6 2 9 5 5 1 4 0

Sample Output 3

21

Sample Input 4

50
12 0 15 15 3 22 7 30 18 5 5 40 1 26 26 9 33 14 14 2 45 11 29 6 6 38 20 4 31 31 8 17 23 23 10 36 13 27 0 19 19 34 16 16 28 21 21 35 24 12

Sample Output 4

343

Sample Input 5

1
1000000000

Sample Output 5

0