Description

伊瑟拉陷入了无限的沉睡之中，它的梦境是由 \(n\) 个点组成的，每个点都有一个权值 \(a_i\)，对与两个不同的点我们可以花费大小为他们权值差的绝对值的代价将这两个点联通，如果所有的点都联通了，伊瑟拉将从梦境中醒来。请你帮帮它，用最少的代价将伊瑟拉唤醒。

Format

Input

第一行为一个正整数 \(n\)，表示点的个数。
第二行有 \(n\) 个非负整数\(a_1,a_2,a_3\)...表示每个点的权值。

Output

一行一个数，表示最少代价。

Sample 1

Input

3
1 2 3

Output

2

Limitation

对于 40%的数据，\(n \le 2000\)
对于 100%的数据，\( n \le 30000,a_i \le 10^9\)