GOLD 2013: The Cow Run

#pragma GCC optimize("O4,unroll-loops")
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
#define endl '\n'
#endif

template<typename T>
bool ckmin(T &a, T b) {
   return a > b ? a = b, true : false;
}

using ll = long long;

const int NMAX = 1005;
const ll INF = 1e18+5;

int n;
int a[NMAX];
ll dp[2][NMAX][NMAX];

void read() {
   cin >> n;
   for (int i = 1; i <= n; i++) {
      cin >> a[i];
   }
}

ll solve() {
   a[++n] = 0;
   sort(a + 1, a + n + 1);

   int john = 0;
   for (int i = 1; i <= n; i++) {
      if (a[i] == 0) {
         john = i;
         break;
      }
   }

   for (int i = 1; i <= john; i++) {
      fill(dp[0][i] + john, dp[0][i] + n + 1, INF);
      fill(dp[1][i] + john, dp[1][i] + n + 1, INF);
   }

   dp[0][john][john] = dp[1][john][john] = 0;

   for (int l = john; l >= 1; l--) {
      for (int r = john; r <= n; r++) {
         ckmin(dp[0][l - 1][r], dp[0][l][r] + 1ll * (a[l] - a[l - 1]) * (n - r + l - 1));
         ckmin(dp[0][l - 1][r], dp[1][l][r] + 1ll * (a[r] - a[l - 1]) * (n - r + l - 1));
         ckmin(dp[1][l][r + 1], dp[0][l][r] + 1ll * (a[r + 1] - a[l]) * (n - r + l - 1));
         ckmin(dp[1][l][r + 1], dp[1][l][r] + 1ll * (a[r + 1] - a[r]) * (n - r + l - 1));
      }
   }

   return min(dp[0][1][n], dp[1][1][n]);
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#else
   freopen("cowrun.in", "r", stdin);
   freopen("cowrun.out", "w", stdout);
#endif

   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);

   read();
   cout << solve() << endl;

   return 0;
}