Increasing Array

Source: CSES

Version: Phuoc Hung OJ Extended

Problem

Given $A=(a_1,\ldots,a_n)$, one move increases one chosen element by 1. Find the minimum number of moves needed to make the array nondecreasing, i.e. $a_i\ge a_{i-1}$ for every $2\le i\le n$.

Input

The first line contains $n$. The second line contains $a_1,\ldots,a_n$.

Output

Print the minimum number of moves; use a 64-bit accumulator.

Subtask

Subtask 1 (20 points): $1\le n\le10$, $a_i\le10^3$.

Subtask 2 (30 points): $1\le n\le1000$, $a_i\le10^9$.

Subtask 3 (50 points): $1\le n\le2\cdot10^5$, $1\le a_i\le10^9$.

Example

Input

5
3 2 5 1 7

Output

5

Explanation

Raise 2 to 3 (1 move) and 1 to 5 (4 moves), for 5 moves total.