Increasing Array

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Given n positive integers, you may increase one element by one per move. Find the minimum moves to make each element at least as large as its predecessor. Decreasing and reordering are not allowed.

Input

First line: n (1<=n<=200000). Next line: n integers, 1<=a_i<=10^9.

Output

Print the minimum number of moves as a signed 64-bit integer.

Subtasks

• Subtask 1 (20%): $n\le10,a_i\le10$.
• Subtask 2 (30%): $n\le1000,a_i\le10^4$.
• Subtask 3 (50%): $n\le200000,a_i\le10^9$ (miền CSES đầy đủ).

Examples

Example 1

Input:

5
3 2 5 1 7

Output:

5

Explanation:

Increase 2 to 3 and 1 to 5, for five moves.

Example 2

Input:

1
1000000000

Output:

0

Explanation:

One element is already nondecreasing.