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

To check your solution you need to sign in
Sign in to continue