CF#715 div2

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cstring>
#include<string>
#include <iomanip>
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;
int s[2005];
ll d[2005][2005];
int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
    }
    sort(s + 1, s + n + 1);
    for (int i = 1; i <= n; i++) {
        d[i][i] = 0;
    }
    for (int dis = 1; dis < n; dis++) {
        for (int i = 1; i + dis <= n; i++) {
            d[i][i + dis] = s[i + dis] - s[i] 
                + min(d[i + 1][i + dis], d[i][i + dis - 1]);
        }
    }
    cout << d[1][n];
}