#include<iostream>
#include<vector>
#include<cassert>

#include <cassert>
#include <vector>


#include <cassert>
#include <numeric>
#include <type_traits>

namespace atcoder {

namespace internal {

#ifndef _MSC_VER
template <class T>
using is_signed_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value ||
                                  std::is_same<T, __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int128 =
    typename std::conditional<std::is_same<T, __uint128_t>::value ||
                                  std::is_same<T, unsigned __int128>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using make_unsigned_int128 =
    typename std::conditional<std::is_same<T, __int128_t>::value,
                              __uint128_t,
                              unsigned __int128>;

template <class T>
using is_integral = typename std::conditional<std::is_integral<T>::value ||
                                                  is_signed_int128<T>::value ||
                                                  is_unsigned_int128<T>::value,
                                              std::true_type,
                                              std::false_type>::type;

template <class T>
using is_signed_int = typename std::conditional<(is_integral<T>::value &&
                                                 std::is_signed<T>::value) ||
                                                    is_signed_int128<T>::value,
                                                std::true_type,
                                                std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<(is_integral<T>::value &&
                               std::is_unsigned<T>::value) ||
                                  is_unsigned_int128<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<
    is_signed_int128<T>::value,
    make_unsigned_int128<T>,
    typename std::conditional<std::is_signed<T>::value,
                              std::make_unsigned<T>,
                              std::common_type<T>>::type>::type;

#else

template <class T> using is_integral = typename std::is_integral<T>;

template <class T>
using is_signed_int =
    typename std::conditional<is_integral<T>::value && std::is_signed<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using is_unsigned_int =
    typename std::conditional<is_integral<T>::value &&
                                  std::is_unsigned<T>::value,
                              std::true_type,
                              std::false_type>::type;

template <class T>
using to_unsigned = typename std::conditional<is_signed_int<T>::value,
                                              std::make_unsigned<T>,
                                              std::common_type<T>>::type;

#endif

template <class T>
using is_signed_int_t = std::enable_if_t<is_signed_int<T>::value>;

template <class T>
using is_unsigned_int_t = std::enable_if_t<is_unsigned_int<T>::value>;

template <class T> using to_unsigned_t = typename to_unsigned<T>::type;

}  // namespace internal

}  // namespace atcoder


namespace atcoder {

template <class T> struct fenwick_tree {
    using U = internal::to_unsigned_t<T>;

  public:
    fenwick_tree() : _n(0) {}
    explicit fenwick_tree(int n) : _n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p && p < _n);
        p++;
        while (p <= _n) {
            data[p - 1] += U(x);
            p += p & -p;
        }
    }

    T sum(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return sum(r) - sum(l);
    }

  private:
    int _n;
    std::vector<U> data;

    U sum(int r) {
        U s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

}  // namespace atcoder

using namespace std;
int N,A[5<<17];
vector<int>IDX[1<<20];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	atcoder::fenwick_tree<long long>SUM(N+N);
	atcoder::fenwick_tree<int>CNT(N+N);
	for(int i=0;i<N;i++)
	{
		cin>>A[i];
		IDX[A[i]].push_back(i);
		SUM.add(i,A[i]);
		SUM.add(i+N,A[i]);
	}
	vector<pair<int,long long> >dp;
	dp.push_back(make_pair(0,0LL));
	for(int a=(int)1e6;a>=1;a--)if(!IDX[a].empty())
	{
		{
			const int sz=IDX[a].size();
			for(int i=0;i<sz;i++)IDX[a].push_back(IDX[a][i]+N);
		}
		{
			const int sz=dp.size();
			for(int i=0;i<sz;i++)dp.push_back(make_pair(dp[i].first+N,dp[i].second));
		}
		for(int i:IDX[a])CNT.add(i,1);
		const int sz=IDX[a].size();
		vector<long long>ndp(sz,(long long)1e18);
		auto upd=[&](int i,long long c){ndp.at(i)=min(ndp[i],c);};
		auto sum0=[&](int l,int r){return SUM.sum(l,r)-(long long)a*CNT.sum(l,r);};
		auto sum1=[&](int l,int r){return SUM.sum(l,r);};
		{
			int r=0;
			for(auto[i,c]:dp)
			{
				while(r<sz&&IDX[a][r]<i)r++;
				if(r+sz/2<=sz)upd(r+sz/2-1,c+sum0(i,IDX[a][r+sz/2-1]));
				if(r>=sz/2)upd(r-sz/2,c+sum1(IDX[a][r-sz/2],i));
			}
		}
		{
			long long nc=1e18;
			int dpi=dp.size()-1;
			for(int i=sz-1;i>=0;i--)
			{
				while(dpi>=0&&dp[dpi].first>=IDX[a][i])
				{
					nc=min(nc,dp[dpi].second+sum1(IDX[a][i],dp[dpi].first));
					dpi--;
				}
				if(i<sz/2)upd(i+sz/2-1,nc+sum0(IDX[a][i],IDX[a][i+sz/2-1]));
				if(i>0)nc+=sum1(IDX[a][i-1],IDX[a][i]);
			}
		}
		{
			long long nc=1e18;
			int dpi=0;
			for(int i=0;i<sz;i++)
			{
				while(dpi<dp.size()&&dp[dpi].first<=IDX[a][i])
				{
					nc=min(nc,dp[dpi].second+sum0(dp[dpi].first,IDX[a][i])-(long long)a*CNT.sum(dp[dpi].first,IDX[a][i]));
					dpi++;
				}
				if(i>=sz/2)upd(i-sz/2,nc+sum1(IDX[a][i-sz/2],IDX[a][i]));
				if(i+1<sz)nc+=sum0(IDX[a][i],IDX[a][i+1])-a;
			}
		}
		dp.clear();
		for(int i=0;i<sz/2;i++)
		{
			dp.push_back(make_pair(IDX[a][i],min(ndp[i],ndp[i+sz/2])));
		}
		for(int i:IDX[a])
		{
			CNT.add(i,-1);
			SUM.add(i,-a);
		}
	}
	long long ans=9e18;
	for(auto[_,c]:dp)ans=min(ans,c);
	cout<<ans<<endl;
}