You have an array $A$ of $N$ integers, where the $i$-th element is $A_i$. You can perform reduction on the array:

• Choose an integer $x$ where $1 \le x \le N$, then decrease the values of $A_0, A_1,...,A_{x-1}$ and $A_{x+1}, A_{x+2},...,A_N$ by $1$.

Find the minimum number of reductions needed to perform to make all the values in the array equal. Note that $A_i$ can be negative or positive at all time. It can be proven that it is always possible to perform some reductions to make all values equal.

Input

The first line of input contains a positive integer, $N$.
The second line of input contains $N$ integers, where the $i$-th integer is $A_i$.

Output

Output the minimum number of reductions needed to perform.

Constraints

For all cases, $1 \le N \le 5\times10^5, 1 \le A_i \le 10^9$
Subtask 1 (20%): $N = 3$
Subtask 2 (20%): $1 \le N \le 50$
Subtask 3 (60%): No additional constraints