Find Minimum Sum (Non-Decreasing Servers)

One operation chooses any contiguous range and increases each element in it by x≥0, at a cost of x rather than the range length times x. Find the minimum total cost to make the array non-decreasing.

输入格式

The first line contains n (1..100000), and the second line contains n power values (1..10⁹).

输出格式

Output a single integer answer.

样例 1

输入：

5
3 4 1 6 2

输出：

7

样例 2

输入：

3
1 2 3

输出：

0

样例 3

输入：

3
5 1 1

输出：

4

样例说明

Example 1: 4→1 drops by 3 and 6→2 drops by 4, so the cost is 7. Example 2: already non-decreasing, cost 0. Example 3: add 4 to the last two elements together, giving 5, 5, 5, cost 4.