Minimum Increments to Nondecreasing

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem Statement

Given n nonnegative integers, one operation increments a chosen element by exactly one. Find the minimum operations required to make the sequence nondecreasing. Decreasing or reordering elements is forbidden.

Input

The first line contains n (1<=n<=100000); the next line contains n integers with 0<=a_i<=10^9.

Output

Print the minimum total number of increment-by-one operations as a 64-bit integer.

Subtasks

• Subtask 1 (20%): $n\le5,a_i\le10$.
• Subtask 2 (30%): $n\le500,a_i\le10^4$.
• Subtask 3 (50%): $n\le100000,a_i\le10^9$.

Examples

Example 1

Input:

5
3 2 5 1 7

Output:

5

Explanation:

Increase 2 to 3 (one move) and 1 to 5 (four moves).

Example 2

Input:

4
9 0 0 0

Output:

27

Explanation:

Each of the three zeros must increase to nine.