#include <map>
#include <set>
#include <array>
#include <cmath>
#include <deque>
#include <bitset>
#include <random>
#include <string>
#include <vector>
#include <cassert>
#include <complex>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

const long long INF = 1e18;

const int MAXN = 500'500;

long long fenw[MAXN];

void add(int i, long long x) {
  for (; i < MAXN; i = (i | (i + 1)))
    fenw[i] += x;
}

long long get(int i) {
  long long ans = 0;
  for (; i >= 0; i = (i & (i + 1)) - 1)
    ans += fenw[i];
  return ans;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  ++n;
  vector<long long> A(n);
  for (int i = 1; i < n; ++i)
    cin >> A[i];
  A[0] = 1'000'001;
  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  stable_sort(order.begin(), order.end(), [&A](int a, int b) {
    return A[a] > A[b];
  });
  long long sum = 0;
  for (int i = 0; i < n; ++i) {
    add(i, A[i]);
    sum += A[i];
  }
  add(0, -A[0]);
  sum -= A[0];

  vector<long long> dp(n, INF);
  dp[0] = 0;
  long long extra = 0;

  vector<int> green;
  vector<int> blue;
  green.emplace_back(0);
  
  vector<long long> pref(n);
  vector<int> before(n);

  int j = 1;

  auto get_orient_sum = [&](int l, int r) {
    if (r >= l)
      return pref[r] - pref[l];
    return pref[r] + sum - pref[l];
  };


  multiset<long long> S;
  vector<int> todo;

  for (; j < n;) {
    long long x = A[order[j]];
    int r = j;
    while (r < n && A[order[r]] == x) {
      blue.emplace_back(order[r]);
      ++r;
    }
    j = r;
    for (int j : blue) {
      add(j, -A[j]);
      sum -= A[j];
    }
    for (int j : blue) {
      pref[j] = get(j);
    }
    int blues = blue.size();

    for (int j = 0; j < blue.size(); ++j)
      before[blue[j]] = j;
    int kek = 0;
    for (int j : green) {
      while (kek < blue.size() && blue[kek] < j)
        ++kek;
      before[j] = kek;
    }

    for (int j : green) {
      //cerr << j << ' ' << dp[j] + extra << '\n';
      pref[j] = get(j);
    }
    extra += sum;

    // left to right
    if (blue.size() == 1) {
      int b = blue.front();
      for (int g : green) {
        dp[b] = min(dp[b], dp[g] - get_orient_sum(g, b) + x * blues);
      }
    } else {
      S.clear();
      todo.clear();
      int p = blue.back();
      for (int g : green) {
        if (g < p)
          S.emplace(dp[g] - pref[g] + sum + x * before[g]);
        else
          todo.emplace_back(g);
      }
      int i1 = 0, i2 = 0;
      while (i1 < blue.size()) {
        if (i1 < blue.size() && (i2 == green.size() || blue[i1] < green[i2])) {
          int b = blue[i1];
          ++i1;
          if (!S.empty()) {
            dp[b] = min(dp[b], *S.begin() + pref[p] - get_orient_sum(p, b) - x * before[b]);
          }
          for (int g : todo) {
            dp[b] = min(dp[b], dp[g] - get_orient_sum(g, b) + x * blues);
            S.emplace(dp[g] - pref[g] + x * before[g] + x * blues);
          }
          todo.clear();
          p = b;
        } else {
          int g = green[i2];
          ++i2;
          S.erase(S.find(dp[g] - pref[g] + sum + x * before[g]));
          todo.emplace_back(g);
        }
      }
    }
    // right to left
    if (blue.size() == 1) {
      int b = blue.front();
      for (int g : green) {
        dp[b] = min(dp[b], dp[g] - get_orient_sum(b, g));
      }
    } else {
      S.clear();
      todo.clear();
      int p = blue.front();
      for (int g : green) {
        if (g > p)
          S.emplace(dp[g] + pref[g] + x * before[g]);
        else
          todo.emplace_back(g);
      }
      int i1 = int(blue.size()) - 1, i2 = int(green.size()) - 1;
      while (i1 >= 0) {
        if (i1 >= 0 && (i2 == -1 || blue[i1] > green[i2])) {
          int b = blue[i1];
          --i1;
          if (!S.empty()) {
            dp[b] = min(dp[b], *S.begin() - pref[p] - get_orient_sum(b, p) - x * before[p]);
          }
          for (int g : todo) {
            dp[b] = min(dp[b], dp[g] - get_orient_sum(b, g));
            S.emplace(dp[g] + pref[g] + sum + x * before[g] + x * blues);
          }
          todo.clear();
          p = b;
        } else {
          int g = green[i2];
          --i2;
          S.erase(S.find(dp[g] + pref[g] + x * before[g]));
          todo.emplace_back(g);
        }
      }
    }

    swap(green, blue);
    blue.clear();
  }


  long long ans = INF;
  for (int g : green)
    ans = min(ans, dp[g]);
  cout << ans + extra << '\n';
  return 0;
}