#include <bits/stdc++.h>
using namespace std;
const long long maxn = 500005;
long long n, ans, tot, sum;
long long a[maxn], s[maxn], c[maxn], tmp[maxn];
priority_queue<long long> q;
inline long long cmp(long long a, long long b) { return a > b; }
signed main() {
  scanf("%lld", &n);
  for (long long i = 1; i <= n; i++) scanf("%lld", &a[i]), ans += a[i];
  sort(a + 1, a + 1 + n, cmp);
  for (long long i = 1; i <= n; i++) {
    if (i == 1 || a[i] != a[i - 1])
      s[++tot] = a[i], c[tot]++;
    else
      c[tot]++;
  }
  for (long long i = 1; i <= tot; i++) {
    long long ok = min(sum - (long long)q.size() * 2, c[i]), tmps = 0,
              rst = min(c[i] - ok, sum - ok);
    for (long long j = 1; j <= ok; j++) tmp[++tmps] = s[i];
    for (long long j = 1; j <= rst; j += 2) {
      long long k = -q.top();
      q.pop();
      if (k < s[i]) {
        tmp[++tmps] = s[i];
        if (j < rst) tmp[++tmps] = s[i];
      } else {
        tmp[++tmps] = k;
        if (j < rst) tmp[++tmps] = 2 * s[i] - k;
      }
    }
    for (long long j = 1; j <= tmps; j++)
      if (tmp[j] >= 0) q.push(-tmp[j]);
    sum += c[i];
  }
  while (!q.empty()) ans += q.top(), q.pop();
  printf("%lld\n", ans);
  return 0;
}
