#include <bits/stdc++.h>
using namespace std;

#define int long long

ifstream fin("podm.in");
ofstream fout("podm.out");

struct arc {
    int u, v, low;
    int base, mul;
    int num, den;

    bool inside(const arc &x) const {
        return u <= x.u && x.v <= v;
    }

    int val() const {
        return num / den;
    }

    bool operator < (const arc &x) const {
        return val() < x.val();
    }

    bool operator <= (const arc &x) const {
        return val() <= x.val();
    }
};

int larp(vector<int> a) {
    int n = a.size();

    if(n < 2)
        return 0;

    if(n == 2)
        return a[0] * a[1];

    a.insert(a.begin(), 0);

    int p = 1;

    for(int i = 2; i <= n; i++)
        if(a[i] < a[p])
            p = i;

    rotate(a.begin() + 1, a.begin() + p, a.begin() + n + 1);

    a.push_back(a[1]);

    vector<int> pref(n + 2);

    for(int i = 1; i <= n + 1; i++)
        pref[i] = pref[i - 1] + a[i] * a[i - 1];

    vector<arc> h(1);

    auto add_arc = [&](int l, int r) {
        arc x;

        x.u = l;
        x.v = r;
        x.low = (a[l] < a[r] ? l : r);
        x.mul = a[l] * a[r];
        x.base = pref[r] - pref[l] - x.mul;
        x.num = x.den = 0;

        h.push_back(x);
    };

    vector<pair<int, int>> tmp, lst;
    vector<int> st;

    for(int i = 1; i <= n; i++) {
        while(st.size() >= 2 && a[st.back()] > a[i]) {
            tmp.push_back({st[st.size() - 2], i});
            st.pop_back();
        }

        st.push_back(i);
    }

    while(st.size() >= 4) {
        tmp.push_back({1, st[st.size() - 2]});
        st.pop_back();
    }

    for(auto [l, r] : tmp)
        if(l != 1 && r != 1)
            lst.push_back({l, r});

    add_arc(1, n + 1);

    vector<vector<int>> fii(2 * n + 5);

    st.clear();

    for(auto [l, r] : lst) {
        add_arc(l, r);

        int x = h.size() - 1;

        while(!st.empty() && h[x].inside(h[st.back()])) {
            fii[x].push_back(st.back());
            st.pop_back();
        }

        st.push_back(x);
    }

    while(!st.empty()) {
        fii[1].push_back(st.back());
        st.pop_back();
    }

    int m = h.size();

    vector<int> sub(m + 1);
    vector<int> qid(m + 1);

    vector<priority_queue<arc>> pq(m + 1);
    vector<vector<arc>> con(n + 2);

    int cntq = 0;

    auto mn_mul = [&](int node) -> int {
        if(node == 1)
            return a[1] * a[2] + a[1] * a[n];

        arc &cur = h[node];

        if(cur.u == cur.low) {
            if(con[cur.u].empty() ||
               !cur.inside(con[cur.u].back()))
                return a[cur.u] * a[cur.u + 1];

            return con[cur.u].back().mul;
        }

        if(con[cur.v].empty() ||
           !cur.inside(con[cur.v].back()))
            return a[cur.v] * a[cur.v - 1];

        return con[cur.v].back().mul;
    };

    auto push_arc = [&](int node, arc x) {
        pq[qid[node]].push(x);

        con[x.u].push_back(x);
        con[x.v].push_back(x);
    };

    auto pop_arc = [&](int node) {
        arc x = pq[qid[node]].top();

        con[x.u].pop_back();
        con[x.v].pop_back();

        pq[qid[node]].pop();
    };

    function<void(int)> dfs = [&](int node) {
        arc &cur = h[node];

        sub[node] = 1;

        if(fii[node].empty()) {
            qid[node] = ++cntq;

            cur.den = cur.base;
            cur.num =
                a[cur.low] *
                (cur.den + cur.mul - mn_mul(node));

            push_arc(node, cur);

            return;
        }

        cur.den = cur.base;

        for(auto x : fii[node]) {
            dfs(x);

            sub[node] += sub[x];
            cur.den -= h[x].base;
        }

        cur.num =
            a[cur.low] *
            (cur.den + cur.mul - mn_mul(node));

        int big = -1;

        for(auto x : fii[node])
            if(big == -1 || sub[x] > sub[big])
                big = x;

        qid[node] = qid[big];

        for(auto x : fii[node]) {
            if(x == big)
                continue;

            while(!pq[qid[x]].empty()) {
                pq[qid[node]].push(pq[qid[x]].top());
                pq[qid[x]].pop();
            }
        }

        auto &q = pq[qid[node]];

        while(!q.empty() &&
              q.top().val() >= a[cur.low]) {
            arc x = q.top();

            cur.den += x.den;

            pop_arc(node);

            cur.num =
                a[cur.low] *
                (cur.den + cur.mul - mn_mul(node));
        }

        while(!q.empty() &&
              cur <= q.top()) {
            arc x = q.top();

            cur.den += x.den;

            pop_arc(node);

            cur.num += x.num;
        }

        push_arc(node, cur);
    };

    dfs(1);

    int ans = 0;

    while(!pq[qid[1]].empty()) {
        ans += pq[qid[1]].top().num;
        pq[qid[1]].pop();
    }

    return ans;
}

signed main() {
    
    int n;
    fin >> n;
    vector<int> v(n + 1);
    for(int i = 0; i < n + 1; i++)
        fin >> v[i];
    fout << larp(v);
    
    return 0;
}