#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second

using ll = long long;

const int N = 1e6 + 7;

int n;
ll a[N], dp[N];

struct Line{
    ll m, b;
    ll get(ll x){
        return m * x + b;
    }
};

bool bad(Line l1, Line l2, Line l3){
    return (__int128)(l2.b - l1.b) * (l2.m - l3.m)
         >= (__int128)(l3.b - l2.b) * (l1.m - l2.m);
}

int main(){
    faster;

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = max(a[i], a[i-1]);
    }

    deque<Line> dq;
    dq.push_back({0, 0});

    for(int i = 1; i <= n; i++){
        ll x = a[i];

        while(dq.size() >= 2 && dq[0].get(x) >= dq[1].get(x))
            dq.pop_front();

        dp[i] = dq.front().get(x) + n * x;

        Line cur = {-i, dp[i]};

        while(dq.size() >= 2 && bad(dq[dq.size()-2], dq.back(), cur))
            dq.pop_back();

        dq.push_back(cur);
    }

    cout << dp[n];
}