#959 Sorting a Sequence 4

Statement

Statement language

A sequence $A$ of length $N$ is sorted if $A_i \leq A_{i+1}$ for every $1 \leq i < N$ .

You may perform the following operation zero or more times: choose an integer $k$ with $1 \leq k \leq N$ , add $1$ to $A_k$ , and subtract from every other element.

Elements may become negative during or after the operations. Every sequence can be made sorted using these operations. Find the minimum number of operations required to sort $A$ .

Input

The input is given in the following format.

$N$ $A_1\ A_2\ \cdots\ A_N$

Output

Print the minimum number of operations.

Constraints

$1 \leq N \leq 100\,000$ .
$0\leq A_i\leq10^9$ ().

Subtasks

#	Score	Constraints
1	13	$N\leq20$ . $A_i\leq1\ (1\leq i\leq N)$ .

Samples

Sample 1

Input

3
3 1 2

Output

2

Sample 2

Input

2
1000000000 0

Output

500000000

Sample 3

Input

6
1000000000 0 1000000000 0 1000000000 0

Output

1500000000