The student council is preparing for the relay race at the sports festival.

The council consists of n members. They will run one after the other in the race, the speed of member i is s_i. The discrepancy d_i of the i-th stage is the difference between the maximum and the minimum running speed among the first i members who ran. Formally, if a_i denotes the speed of the i-th member who participated in the race, then d_i = max(a_1, a_2, ..., a_i) - min(a_1, a_2, ..., a_i).

You want to minimize the sum of the discrepancies d_1 + d_2 + ... + d_n. To do this, you are allowed to change the order in which the members run. What is the minimum possible sum that can be achieved?

Input

The first line contains a single integer n (1 ≤ n ≤ 2000) — the number of members of the student council.

The second line contains n integers s_1, s_2, ..., s_n (1 ≤ s_i ≤ 10^9) – the running speeds of the members.

Output

Print a single integer — the minimum possible value of d_1 + d_2 + ... + d_n after choosing the order of the members.

Examples

Input


3
3 1 2


Output


3


Input


1
5


Output


0


Input


6
1 6 3 3 6 3


Output


11


Input


6
104 943872923 6589 889921234 1000000000 69


Output


2833800505

Note

In the first test case, we may choose to make the third member run first, followed by the first member, and finally the second. Thus a_1 = 2, a_2 = 3, and a_3 = 1. We have:

  * d_1 = max(2) - min(2) = 2 - 2 = 0. 
  * d_2 = max(2, 3) - min(2, 3) = 3 - 2 = 1. 
  * d_3 = max(2, 3, 1) - min(2, 3, 1) = 3 - 1 = 2. 



The resulting sum is d_1 + d_2 + d_3 = 0 + 1 + 2 = 3. It can be shown that it is impossible to achieve a smaller value.

In the second test case, the only possible rearrangement gives d_1 = 0, so the minimum possible result is 0.


import java.awt.*;
import java.io.*;
import java.util.List;
import java.util.*;

public class Main {

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;

        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    } else {
                        continue;
                    }
                }
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');

            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }
//
//

    //    static class TreeNode {
//        int val;
//        TreeNode left,right;
//        TreeNode(int val){
//            this.val=val;left=null;right=null;
//        }
//    }
//    static TreeNode maxx(int start,int end,int[] arr){
//        if(start>end){
//            return null;
//        }
//        int ind=0;
//        int max=-1;
//        for(int j=start;j<=end;j++){
//            if(arr[j]>max){
//                max=arr[j];
//                ind=j;
//            }
//        }
//        TreeNode jj=new TreeNode(arr[ind]);
//        jj.left=maxx(start,ind-1,arr);
//        jj.right=maxx(ind+1,end,arr);
//        return jj;
//
//    }
//    static void dfs(TreeNode root,int dep){
//        if(root==null){
//            return;
//        }
//        ans[hashMap.get(root.val)]=dep;
//        dfs(root.left,dep+1);
//        dfs(root.right,dep+1);
//    }
//    static int[] ans;
//   static HashMap<Integer,Integer> hashMap;
//   static class pont{
//       int val,index;
//       pont(int val,int index){
//           this.val=val;
//           this.index=index;
//       }
//   }
//   static class compr implements Comparator<pont>{
//       public int compare(pont a,pont b){
//           return a.val-b.val;
//       }
//   }
//    static class poin{
//       int src;
//       long val;
//       poin(int src,long val){
//           this.src=src;
//           this.val=val;
//       }
//    }
//
//    static double maxx(int flag,String s,String t,int k){
//
//       if(flag==0){
//
//           StringBuilder stringBuilder = new StringBuilder(s.substring(0,s.length()-1));
//           double ans= 0.0;
//           for(int j=1;j<10;j++){
//               StringBuilder str=new StringBuilder(stringBuilder);
//               str.append(j);
//
//               ans=(double)((double)ans+(double)maxx(1,str.toString(),t,k));
//           }
//           return ans;
//       }
//       else if(flag==1){
//
//           StringBuilder stringBuilder = new StringBuilder(t.substring(0,t.length()-1));
//           double ans= 0.0;
//           for(int j=1;j<10;j++){
//               StringBuilder str=new StringBuilder(stringBuilder);
//               str.append(j);
//               ans=(double)((double)ans+(double)maxx(2,s,str.toString(),k));
//           }
//           return ans;
//
//       }
//       else{
//           long[] count=new long[10];
//           long taka=0;
//           long[] tot=new long[10];
//
//           for(int j=0;j<s.length();j++){
//               int a=Integer.parseInt(String.valueOf(s.charAt(j)));
//               count[a]++;
//               tot[a]++;
//           }
//           for(int j=1;j<10;j++){
//               taka=(long)((long)taka+(long)((long)Math.pow(10,count[j])*(long)j));
//           }
//           long aoki=0;
//           count=new long[10];
//           for(int j=0;j<t.length();j++){
//               int a=Integer.parseInt(String.valueOf(t.charAt(j)));
//               count[a]++;
//               tot[a]++;
//           }
//           for(int j=1;j<10;j++){
//               aoki=(long)((long)aoki+(long)((long)Math.pow(10,count[j])*(long)j));
//           }
//           if(aoki>=taka){
//               return 0;
//           }else{
//               if(t.charAt(t.length()-1)==s.charAt(s.length()-1)){
//                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)2;
//                   return (double)((double)((double)(kk)*(double)(kk-(double)1))/(double)((double)1*((double)9*(double)k-(double)8)*(double)((double)9*(double)k-(double)9)));
//
//               }else{
//                   double kk=(double)k-(double)tot[Integer.parseInt(String.valueOf(t.charAt(t.length()-1)))]+(double)1;
//                   double kk2=(double)k-(double)tot[Integer.parseInt(String.valueOf(s.charAt(s.length()-1)))]+(double)1;
//                   return (double)(((double)((double)1*(double)kk)*(double)(kk2))/(double)((double)1*((double)9*(double)k-(double)8)*(double) ((double)9*(double)k-(double)9)));
//               }
//           }
//
//       }
//
//
//    }
//
//   static void sieveOfEratosthenes(int n)
//    {
//        boolean prime[] = new boolean[n + 1];
//        for (int i = 0; i <= n; i++)
//            prime[i] = true;
//
//        for (int p = 2; p * p <= n; p++)
//        {
//            if (prime[p] == true)
//            {
//                for (int i = p * p; i <= n; i += p)
//                    prime[i] = false;
//            }
//        }
//
//        for (int i = 2; i <= n; i++)
//        {
//            if (prime[i] == true)
//                treeMap.put(i,0);
//        }
//    }
//    static TreeMap<Integer,Integer> treeMap;
    static class comp implements Comparator<Point> {
        public int compare(Point a, Point b) {
            if (b.y == a.y) {
                return a.x - b.x;
            }
            return b.y - a.y;
        }
    }

    static boolean ff = false;

    //    static void maxx(int ind,int l,int r,int d,int u,int n)
//    {
//        if(ind==4){
//            if(l<0 || r<0 || u<0 || d<0){
//                return;
//            }
//            ff=true;
//            return;
//        }
//        if(ind==0){
//            if(l==n){
//                maxx(ind+1,l-2,r,d-1,u-1,n);
//            }else if(l==n-1){
//                maxx(ind+1,l-1,r,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l-1,r,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else if(ind==1){
//            if(r==n){
//                maxx(ind+1,l,r-2,d-1,u-1,n);
//            }else if(r==n-1){
//                maxx(ind+1,l,r-1,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else if(ind==2){
//            if(d==n){
//                maxx(ind+1,l-1,r-1,d-2,u,n);
//            }else if(d==n-1){
//                maxx(ind+1,l-1,r,d-1,u,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d-1,u,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//
//        }else{
//            if(u==n){
//                maxx(ind+1,l-1,r-1,d,u-2,n);
//            }else if(u==n-1){
//                maxx(ind+1,l-1,r,d,u-1,n);
//                if(ff){
//                    return;
//                }
//                maxx(ind+1,l,r-1,d,u-1,n);
//            }else{
//                maxx(ind+1,l,r,d,u,n);
//            }
//        }
//    }
//    static void filereader() throws IOException{
//        FileReader fileReader=new FileReader("input.txt");
//        int ch;
//        String str="";
//        StringBuilder stringBuilder=new StringBuilder();
//        while ((ch=fileReader.read())!=-1)
//            stringBuilder.append((char)ch);
//
//        fileReader.close();
//        StringBuilder ans=new StringBuilder();
//        FileWriter fw=new FileWriter("output.txt");
//        for(int j=0;j<ans.length();j++){
//            fw.write(ans.charAt(j));
//        }
//        fw.close();
//    }
    static class point {
        int w, v;

        point(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }

    static class compp implements Comparator<point> {
        public int compare(point a, point b) {
            return b.v - a.v;
        }
    }

    //    static int cal(int ind,String s,String x,int val){
//        if(ind>=s.length()){
//            if(val%7==0){
//                return 1;
//            }else{
//                return 0;
//            }
//        }
//        if(aa[ind][val]!=-1){
//            return aa[ind][val];
//        }
//
//        if(x.charAt(ind)=='A'){
//            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
//            return aa[ind][val]=Math.min( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
//        }else{
//            int ii=Integer.parseInt(String.valueOf(s.charAt(ind)));
//            return aa[ind][val]=Math.max( cal(ind+1,s,x,(val*10)%7  ),cal(ind+1,s,x, (val*10+ii)%7 )  );
//        }
//
//    }
//    static int aa[][];

    //    static long calculateWays(int ind,int bit,int[] primes,long a,long b,int[] flags){
//
//        long num=(long)((long)ind+(long)a);
//        if(num>b){
//            return 1;
//        }
//        if(aaa[ind][bit]!=-1){
//            return aaa[ind][bit];
//        }
//
//        long tot=0;
////        int flag=0;
////        int bitt=bit;
////        for(int j=0;j<primes.length;j++){
////            int jj= (int)bit & (int)Math.pow(2,j);
////
////            if(jj!=0 && num%(long)primes[j]==0 ){
////                flag=1;
////                break;
////            }
////            if( num%(long)primes[j]==0 ){
////                bitt=(int)bitt | (int)Math.pow(2,j);
////
////            }
////        }
//        int jj=(int)(flags[ind] & (int)bit);
//        if( jj==0){
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit | flags[ind],primes,a,b,flags));
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
//
//        }else{
//            tot=(long)((long)tot+(long)calculateWays(ind+1,bit,primes,a,b,flags));
//        }
//
//        return aaa[ind][bit]=tot;
//    }
    static long[][] aaa;

    static long maxx(String str, int n, long val) {

        if (hashMap.get(str) != null) {
            return hashMap.get(str);
        }
        long tot = 0;
        if (str.equals("")) {
            for (int j = 1; j <= 9; j++) {
                tot = tot + maxx(str + String.valueOf(j), n, val);
            }
            hashMap.put(str, tot);

            return tot;
        } else {
            String ss = str + str;
            if (Long.parseLong(ss) > val) {
                return 0;
            }
            if (str.length() == n) {
                return 1;
            }
            for (int j = 0; j <= 9; j++) {
                tot = tot + maxx(str + String.valueOf(j), n, val);
            }
            hashMap.put(str, tot);
            return tot;
        }

    }

    static class poi {
        int freq, occur, num;

        poi(int freq, int occur, int num) {
            this.freq = freq;
            this.num = num;
            this.occur = occur;
        }
    }

    static class poii {
        int day, tot;

        poii(int day, int tot) {
            this.day = day;
            this.tot = tot;
        }
    }

    static class comp2 implements Comparator<poii> {
        public int compare(poii a, poii b) {
            return a.tot - b.tot;
        }
    }

    static class comp1 implements Comparator<poi> {
        @Override
        public int compare(poi o1, poi o2) {
            if (o2.occur == o1.occur) {
                return o1.freq - o2.freq;
            }
            return o1.occur - o2.occur;
        }
    }

    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    static HashMap<String, Long> hashMap;

    static class poit {
        int freq, val;

        poit(int freq, int val) {
            this.freq = freq;
            this.val = val;
        }
    }

    static class com implements Comparator<poit> {
        public int compare(poit a, poit b) {
            return b.freq - a.freq;
        }
    }


//    static int maxx(int ind,String str,int prev,int x,int y){
//        if(ind>=str.length()){
//            return 0;}
//        if(aa[ind][prev]!=Integer.MAX_VALUE){
//            return aa[ind][prev];}
//        if(str.charAt(ind)=='?' ){
//            if(ind>0){
//                if(prev==1){
//                    if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                             return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x+y );
//
//                    }
//                    else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x,maxx(ind+1,str,2,x,y)+x );
//
//                    }
//                    else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                        return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x );
//                    }
//                    else{
//                        return aa[ind][prev]=Math.min(maxx( ind+1,str,1,x,y ),maxx(ind+1,str,2,x,y)+x);
//                    }
//
//                }
//                else{
//                    if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+y,maxx(ind+1,str,2,x,y)+y );
//
//                    }
//                    else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                        return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x+y,maxx(ind+1,str,2,x,y) );
//
//                    }
//                    else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                        return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y)+y,maxx(ind+1,str,2,x,y) );
//                    }
//                    else{
//                        return aa[ind][prev]=Math.min(maxx( ind+1,str,1,x,y )+y,maxx(ind+1,str,2,x,y));
//                    }
//                }
//            }
//            else{
//                if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                    return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y)+x );
//
//                }
//                else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                    return aa[ind][prev]=Math.min(maxx(ind+1,str,1,x,y)+x,maxx(ind+1,str,2,x,y) );
//
//                }
//                else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                    return aa[ind][prev]=  Math.min(maxx(ind+1,str,1,x,y),maxx(ind+1,str,2,x,y) );
//                }
//                else{
//                    return aa[ind][prev]=0;
//                }
//            }
//        }else if(str.charAt(ind)=='C'){
//            if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                return aa[ind][prev]=maxx(ind+1,str,1,x,y);
//
//            }
//            else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                return aa[ind][prev]=maxx(ind+1,str,1,x,y)+x;
//
//            }
//            else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                return aa[ind][prev]=  maxx(ind+1,str,1,x,y);
//            }
//            else{
//                return aa[ind][prev]=0;
//            }
//        }
//        else{
//            if( ind+1 < str.length() && str.charAt(ind+1) == 'C' ){
//                return aa[ind][prev]=maxx(ind+1,str,2,x,y)+y;
//
//            }
//            else if(ind+1<str.length() && str.charAt(ind+1)=='J' ){
//                return aa[ind][prev]=maxx(ind+1,str,2,x,y);
//
//            }
//            else if(ind+1<str.length() && str.charAt(ind+1)=='?'){
//                return aa[ind][prev]=  maxx(ind+1,str,2,x,y);
//            }
//            else{
//                return aa[ind][prev]=0;
//            }
//        }
//    }
//    static int[][] aa;
//    static int totalCost(int[] arr,int[] arr1,int n){
//        HashMap<Integer,Integer> has=new HashMap<>();
//        for(int i=0;i<n;i++){
//
//            has.put(arr[i],i );
//
//        }
//        Arrays.sort(arr1);
//        int tot=0;
//        for(int i=0;i<n-1;i++){
//            tot=tot+has.get(arr1[i])-i+1;
//            int tta=has.get(arr1[i]);
//            for(int j=tta;j>=i;j-- ){
//                has.put(arr[j],tta-j+i );
//
//            }
//            int low=i;
//            int high=tta;
//            while(low<high){
//                int temp=arr[low];
//                arr[low]=arr[high];
//                arr[high]=temp;
//                low++;high--;
//            }
//
//        }
//        return tot;
//
//    }
//    static boolean fff=false;
//    static HashSet<String> hashSet=new HashSet<>();
//    static void maxx(int ind,int[] arr,HashSet<Integer> has,int n,String str,int cost){
//        if(ind==n){
//            int to=totalCost(arr,arr,n);
//            if(to==cost){
//                fff=true;
//            }
//            return;
//        }
//        if(hashSet.contains(str)){
//            return ;
//        }
//        for(int j=1;j<=n;j++){
//            if(!has.contains(j)){
//                arr[ind]=j;
//                has.add(j);
//                maxx(ind+1,arr,has,n,str+String.valueOf(j),cost);
//                has.remove(j);
//            }
//            if(ff){
//                return;
//            }
//        }
//    }
//    static long maxx(int ind,int n,int flag,int k){
//        if(ind>n || ind<0 || k==1){
//            return 0;
//        }
//        if(flag==1 && ind==0){
//            return 0;
//        }
//        if(aaaa[ind][flag][k]!=-1) {
//            return aaaa[ind][flag][k];
//        }
//        if(flag==0){
//            return aaaa[ind][flag][k]=(long)(maxx(ind-1,n,1,k-1)+(long)1+maxx(ind+1,n,0,k))%(long)mod;
//        }
//        else{
//            return aaaa[ind][flag][k]=(long)(maxx(ind+1,n,0,k-1)+(long)1+maxx(ind-1,n,1,k))%(long)mod;
//        }
//
//    }
//
////    static int minimum_change(int ind,int[] arr,int tot,int flag,String str,String temp){
////        if(ind>=arr.length){
////            return 0;
////        }
////        if(tot>=5) {
////            String strr=String.valueOf(arr[ind]);
////            for(int j=0;j<=9;j++) {
////                strr=strr.concat(String.valueOf(j));
////            }
////        }
////    }
//
//    static long[][][] aaaa;
//    static long mod=(long)((long)Math.pow(10,9)+(long)7);
    static List<Integer> ans=new ArrayList<>();
    static void goodVertices(LinkedList<Integer>[] linkedLists,int src,int parent,HashSet<Integer> hashSet,int[] cost){

        int flag=0;
        if(!hashSet.contains(cost[src])){
            hashSet.add(cost[src]);
            ans.add(src+1);
            flag=1;
        }
        for(Integer i:linkedLists[src]){
            if(i==parent){
                continue;
            }
            goodVertices(linkedLists,i,src,hashSet,cost);
        }
        if(flag==1){
            hashSet.remove(cost[src]);
        }

    }
    static boolean fla=false;
//    static void calculate(String[] str,int flag,String str1,String str2){
//        if(flag==0){
//            if(str[0].length()==str1.length()){
//                calculate(str,1,str1,str2);
//                return;
//            }
//            for(int j=0;j<=9;j++){
//                if( j==0 && str1.equals("") ){
//                    continue;
//                }
//                calculate(str,1,str1+String.valueOf(j),str2);
//                if(fla){
//                    break;
//                }
//            }
//        }
//        else if(flag==1){
//            if(str[1].length()==str2.length()){
//                calculate(str,2,str1,str2);
//                return;
//            }
//            int ind=str2.length();
//            if( str[0].length()>ind && str[0].charAt(ind)==str[1].charAt(ind)){
//                calculate(str,1,str1,str2+String.valueOf(str1.charAt(ind)));
//            }else{
//                for(int j=0;j<=9;j++){
//                    if(j==0 && str2.equals("")){
//                        continue;
//                    }
//                    calculate(str,1,str1,str2+String.valueOf(j));
//                }
//            }
//        }
//        else{
//            long n1=Long.parseLong(str1);
//            long n2=Long.parseLong(str2);
//            long n3=(long)((long)n1+(long)n2);
//            if(String.valueOf(n3).length()==str[2].length()){
//
//            }
//
//        }
//    }
static List<Integer> findprime(int n) {
    List<Integer> primes = new ArrayList<>();
    boolean[] prime = new boolean[n];
    for (int j = 1; j < prime.length; j++) {
        prime[j] = true;
    }
    for (int j = 2; j * j < prime.length; j++) {
        if (!prime[j]) {
            continue;
        }
        for (int i = j * j; i < prime.length; i = i + j) {
            prime[i] = false;
        }
    }
    for (int j = 2; j < prime.length; j++) {
        if (prime[j]) {
            String str=String.valueOf(j);
            hashMap1.putIfAbsent(str.length(),new ArrayList<>());
            hashMap1.get(str.length()).add(j);
            primes.add(j);
        }
    }
    return primes;
}
    static long[][] dp;
    static HashMap<Integer,List<Integer>> hashMap1;
    static boolean fff=false;
//    static int cal(int ind,int tot,String str,int[] pre){
//        if(ind>=str.length() && tot==0){
//            fff=true;
//            return 1;
//        }
//        if(ind>=str.length() || tot<0 || tot>=2){
//            return -1;
//        }
//        if(dp[ind][tot]!=0){
//            return dp[ind][tot];
//        }
//
//        if(str.charAt(ind)=='T'){
//            int ii=cal(ind+1,tot+1,str,pre);
//            if(fff){
//                return 1;
//            }
//            int jj=cal(ind+1,tot-1,str,pre);
//            return dp[ind][tot]= Math.max(ii,jj) ;
//
//        }else{
//            int jj=cal(ind+1,tot-1,str,pre);
//            return dp[ind][tot]= jj;
//        }
//
//    }
    static long min;
        static long calculatemin(int low,int high,int[] arr,int flag,long tot){
//            if(tot>=min){
//                return Long.MAX_VALUE;
//            }
//            if(low>=arr.length || high>=arr.length){
//                return Long.MAX_VALUE;
//            }
            if(dp[low][high]!=-1){
                return dp[low][high];
            }
            if( low==high){
                return 0;
            }
            return dp[low][high]=Math.min( calculatemin(low+1,high,arr,0,tot),
                    calculatemin(low,high-1,arr,0,tot)  )+(long)( (long)arr[high]-(long)arr[low] );
//            if(flag==0){
//                return dp[low][high][flag]=Math.min( Long.MAX_VALUE,
//                        calculatemin(low,high+1,arr,1,tot) );
//            }else{
//                if(low==0){
//                    return dp[low][high][flag]=suff[0][high];
//                }else if(high==arr.length-1){
//                    return dp[low][high][flag]=pre[arr.length-1][low];
//                }else{
//                    return dp[low][high][flag]=Math.min(  (long)((long)calculatemin(low-1,high,arr,1,(long)((long)tot+(long)( (long)arr[high]-(long)arr[low] )) )+(long)( (long)arr[high]-(long)arr[low] )),
//                            (long)((long)calculatemin(low,high+1,arr,1,(long)((long)tot+(long)( (long)arr[high]-(long)arr[low] )))+(long)((long)arr[high]-(long)arr[low])) );
//                }
//            }
        }

    public static void main(String[] args) throws IOException {

            Reader reader=new Reader();
            int n=reader.nextInt();
            int[] arr=new int[n];
            for(int j=0;j<n;j++){
                arr[j]=reader.nextInt();
            }
            dp=new long[n][n];
            for(int i=0;i<n;i++){
                //for(int j=0;j<n;j++){
                    Arrays.fill(dp[i],-1);
                //}
            }
//        pre=new long[n][n];
//        suff=new long[n][n];
//
        Arrays.sort(arr);
//        HashMap<Integer,Integer> hashMap=new HashMap<>();
//        HashMap<Integer,Integer> index=new HashMap<>();
//        for(int j=0;j<arr.length;j++){
//            hashMap.put(arr[j],hashMap.getOrDefault(arr[j],0)+1);
//            index.putIfAbsent(arr[j],j);
//        }
//
//            for(int j=0;j<=0;j++){
//                pre[arr.length-1][0]=(long)((long)arr[arr.length-1]-(long)arr[0]);
//                for(int i=1;i<=arr.length-1;i++){
//                    pre[arr.length-1][i]=pre[arr.length-1][i-1]+(long)( (long)arr[arr.length-1]-(long)arr[i] );
//                }
//                suff[j][n-1]=(long)( (long)arr[n-1]-(long)arr[j] );
//                for(int i=n-2;i>=0;i--){
//                    suff[j][i]=(long)suff[j][i+1]+(long)( (long)arr[i]-(long)arr[j] );
//                }
//            }
            if(arr.length==1){
                System.out.println(0);
            }else {
//                int max=0;
//                int in=-1;
//                for(Integer i:hashMap.keySet()){
//                    if(max<hashMap.get(i)){
//                        max=hashMap.get(i);
//
//                    }
//                }
//                List<Integer> list=new ArrayList<>();
//                for(Integer i:hashMap.keySet()){
//                    if(max==hashMap.get(i)){
//                        list.add(index.get(i));
//                    }
//                }
//                min=Long.MAX_VALUE;
//
//
//                for(int j=0;j<n;j++){
//
//                    min=Math.min( calculatemin(j,j,arr,0,0l),min );
//                }
                System.out.println(calculatemin(0,n-1,arr,0,0));
            }
//        BufferedReader scanner=new BufferedReader(new InputStreamReader(System.in));
//        int t= Integer.parseInt(scanner.readLine().trim());
//        for(int j=0;j<t;j++) {
//            int n=Integer.parseInt(scanner.readLine().trim());
//            String str=scanner.readLine().trim();
//            int m=0,ttl=0;
//            int[] pre=new int[n];
//
//            for(int i=0;i<n;i++){
//
//                if(str.charAt(i)=='M'){
//                    m++;
//                }else{
//                    ttl++;
//                }
//                pre[i]=ttl;
//            }
//            if(ttl!=2*m){
//                System.out.println("NO");continue;
//            }
//            int tt=0,mm=0,ttt=0;
//            boolean flag=true;
//            int[] suff=new int[n];
//            int[] sufft=new int[n];
//            for(int i=n-1;i>=0;i--){
//                if(i==n-1){
//                    if(str.charAt(i)=='M'){
//                        suff[i]=1;
//                        sufft[i]=0;
//                    }else{
//                        suff[i]=0;
//                        sufft[i]=1;
//                    }
//                    continue;
//                }
//                if(str.charAt(i)=='M'){
//                    suff[i]=suff[i+1]+1;
//                    sufft[i]=sufft[i+1];
//                }else{
//                    suff[i]=suff[i+1];
//                    sufft[i]=sufft[i+1]+1;
//                }
//
//            }
//int rem=0;
//            for(int i=n-1;i>=0;i--){
//                if(str.charAt(i)=='M'){
//                    if(Math.min(sufft[i],pre[i])<suff[i]-rem){
//                        flag=false;break;
//                    }else{
//                        rem=rem+1;
//                    }
//                }
//            }
////
//
//            if(!flag ){
//                System.out.println("NO");
//            }else{
//
//                    System.out.println("YES");
//
//
//            }
//
//
//        }

        //for (int j = 0; j < t; j++)
        {






//            int a = scanner.nextInt();
//            int b = scanner.nextInt();
//
//            String str=scanner.next();
//            int i=0;
//            int k=a+b-1;
//            char[] ch=str.toCharArray();
//            int flag=0;
//            int val=0;
//            while (i<=k){
//                if(i==k){
//                    if(ch[i]=='?'){
//                        val++;
//                    }else if(ch[i]=='0'){
//                        a--;
//                    }else{
//                        b--;
//                    }
//                    i++;k--;continue;
//                }
//
//                if( (ch[i]=='0' || ch[k]=='0')  ){
//                    ch[i]='0';
//                    ch[k]='0';
//                    a=a-2;
//                }
//                else if( (ch[i]=='1' || ch[k]=='1')  ){
//                    b=b-2;
//                    ch[i]='1';
//                    ch[k]='1';
//                }
//                else {
//                    val+=2;
//                }
//                if(a<0 || b<0){
//                    flag=1;break;
//                }
//                i++;
//                k--;
//            }
//            if(flag==1){
//                System.out.println(-1);
//            }else{
//                if(val==a+b){
//                    String ans=String.valueOf(ch);
//                    System.out.println(ans);
//                }else{
//                    System.out.println(-10);
//                }
//            }



            }






        }








    }








