USACO March 2013 - GOLD

//tonynater - USACO 2013

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;

#define sz(x) ((int) x.size())

typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;

const double pi = 3.141592653589793;
const double tau = 6.283185307179586;
const double epsilon = 1e-6;

const int MAX_N = 1100;

int N;

ll cows[MAX_N];

int low = 0, high = 0;
ll dp[MAX_N][MAX_N][2];
ll minDamage(int l, int h, bool lh)
{
    if(dp[l][h][lh] != -1) return dp[l][h][lh];

    if(l+h == N) return (dp[l][h][lh] = 0);

    ll damage = 1LL<<60;
    if(!lh) //lower
    {
        if(l < low) damage = min((cows[low-l]-cows[low-l-1])*(N-l-h) + minDamage(l+1,h,0), damage);
        if(h < high) damage = min((cows[low+h]-cows[low-l])*(N-l-h) + minDamage(l,h+1,1), damage);
    }else //higher
    {
        if(l < low) damage = min((cows[low+h-1]-cows[low-l-1])*(N-l-h) + minDamage(l+1,h,0), damage);
        if(h < high) damage = min((cows[low+h]-cows[low+h-1])*(N-l-h) + minDamage(l,h+1,1), damage);
    }

    return (dp[l][h][lh] = damage);
}

int main (int argc, const char * argv[])
{
    freopen("cowrun.in", "r", stdin); freopen("cowrun.out", "w", stdout);

    cin >> N;

    for(int i = 0; i < N; i++)
    {
        cin >> cows[i];
        if(cows[i] < 0) ++low;
        else ++high;
    }

    sort(cows, cows+N);

    fill_n(&dp[0][0][0], MAX_N*MAX_N*2, -1);

    ll damage = 1LL<<60;
    if(low > 0) damage = min(-cows[low-1]*N + minDamage(1,0,0), damage); //lower
    if(high > 0) damage = min(cows[low]*N + minDamage(0,1,1), damage); //higher

    cout << damage << '\n';

    return 0;
}