Make it non-decreasing
Given an array of
n integers, you are asked to make it non-decreasing. You are allowed to add 1 to any element in the array as many times as you want. Each time you add 1 to an element, you pay $1. You’d like to make the array non-decreasing but with minimal cost. Can you calculate the minimum amount it will cost you to transform the array?Input
The first line of the input contains a single integer
n (2 ≤ n ≤ ) - the number of elements in the array.The second line of the input contains
n space-separated integers ( ≤ ≤ ) - array elements.Output
The program should print the minimal cost to transform the array into a non-decreasing sequence of numbers.
Examples
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