配列を非減少にする
n 個の整数からなる配列が与えられます。このとき、配列を非減少にすることが求められます。配列の任意の要素に対して、何度でも 1 を加算することができ、そのたびに $1 のコストがかかります。配列を非減少にしつつ、コストを最小限に抑えるにはどうすればよいでしょうか。必要な最小コストを求めてみてください。入力
最初の行には、配列の要素数を表す整数
n (2 ≤ n ≤ ) が与えられます。次の行には、
n 個の整数 ( ≤ ≤ ) が空白区切りで与えられます。出力
配列を非減少な数列に変換するために必要なコストの最小値を出力してください。
例
Input | Output |
4
-2 3 1 0 | 5 |
5
1 2 3 4 4 | 0 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB