#include "histogram.h"
#include <bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v = a; v <= b; v++)
#define fr(v,a,b) for(int v = a; v >= b; v--)
#define cl(a,v) memset(a, v, sizeof(a))

typedef long long ll;

const int N = 5e5 + 10;

int n, a[N], maxh;
ll ans1, ans2, ans3;

inline void upd(ll &x, ll y) {  x = max(x, y);  }

int st[N], top;
int fa[N], lc[N], rc[N], root, siz[N], lb[N], rb[N];

void work(int x) {
    if(x == 0) return ;
    siz[x] = 1, lb[x] = rb[x] = x;
    for(int y : {lc[x], rc[x]}) if(y) {
        work(y), siz[x] += siz[y];
        lb[x] = min(lb[x], lb[y]), rb[x] = max(rb[x], rb[y]);
    }
}
void build() {
    fo(i, 1, n) {
        int tmp = 0;
        while(top && a[st[top]] > a[i])
            rc[st[top]] = tmp, fa[tmp] = st[top], tmp = st[top--];
        fa[tmp] = i, lc[i] = tmp, st[++top] = i;
    }
    st[top + 1] = 0;
    while(top) rc[st[top]] = st[top + 1], fa[st[top + 1]] = st[top], top--;
    root = st[1], work(root);
}

ll pre[N], suf[N];
void solve1() {
    fo(i, 1, n) pre[rb[i]] = max(pre[rb[i]], (ll)a[i] * siz[i]);
    fo(i, 1, n) pre[i] = max(pre[i - 1], pre[i]);
    ans1 = pre[n];
}

struct line {  int k; ll b;  } ;
inline ll eval(const line &v, int x) {  return (ll)v.k * x + v.b;  }
struct node {  int lc, rc; line v;  } t[N];
int rt[N], tot;
inline void reset() {  cl(t, 0), cl(rt, 0), tot = 0;  }
void insert(int &p, int l, int r, line cur, int now = 0) {
    if(p == 0) return p = (now ? now : ++tot), t[p].v = cur, void();
    if(l == r) {
        if(eval(cur, l) > eval(t[p].v, l)) swap(t[p].v, cur);
        return ;
    }
    int mid = (l + r) >> 1;
    if(eval(cur, mid) > eval(t[p].v, mid)) swap(cur, t[p].v);
    if(eval(cur, l) > eval(t[p].v, l))
        insert(t[p].lc, l, mid, cur, now);
    else insert(t[p].rc, mid + 1, r, cur, now);
}
ll query(int p, int l, int r, int x) {
    if(p == 0) return 0;
    ll res = (ll)t[p].v.k * x + t[p].v.b;
    int mid = (l + r) >> 1; if(l == r) return res;
    if(x <= mid) return max(res, query(t[p].lc, l, mid, x));
    else return max(res, query(t[p].rc, mid + 1, r, x));
}
int merge(int p, int q, int l, int r) {
    if(!p || !q) return p | q;
    if(l == r) {
        if(eval(t[p].v, l) < eval(t[q].v, l)) swap(t[p].v, t[q].v);
        return p;
    }
    int mid = (l + r) >> 1;
    t[p].lc = merge(t[p].lc, t[q].lc, l, mid);
    t[p].rc = merge(t[p].rc, t[q].rc, mid + 1, r);
    return t[q].lc = t[q].rc = 0, insert(p, l, r, t[q].v, q), p;
}

ll res[N]; line arr[N];
void dfs(int x) {
    if(x == 0) return ;
    dfs(lc[x]), dfs(rc[x]);
    rt[x] = merge(rt[lc[x]], rt[rc[x]], 1, maxh);
    res[x] = query(rt[x], 1, maxh, a[x]) + arr[x].b;
    insert(rt[x], 1, maxh, arr[x]);
}

void solve2() {
    ans2 = ans1;
    // Case 1
    fo(i, 1, n) suf[lb[i]] = max(suf[lb[i]], (ll)a[i] * siz[i]);
    fr(i, n, 1) suf[i] = max(suf[i + 1], suf[i]);
    fo(i, 1, n + 1) ans2 = max(ans2, pre[i - 1] + suf[i]);
    // Case 2
    fo(i, 1, n) arr[i] = {-siz[i], (ll)siz[i] * a[i]};
    dfs(root);
    fo(i, 1, n) ans2 = max(ans2, res[i]);
}

void dfs2(int x) {
    if(x == 0) return ;
    dfs2(lc[x]), dfs2(rc[x]);
    rt[x] = merge(rt[lc[x]], rt[rc[x]], 1, maxh);
    ans3 = max(ans3, query(rt[x], 1, maxh, a[x]) + arr[x].b);
    insert(rt[x], 1, maxh, {-siz[x], res[x]});
}

ll val[N];
struct SegTree {
    struct segnode {
        int l, r; vector<line> L, R;
    } tr[N << 2];
    void build(int p, int l, int r) {
        tr[p].l = l, tr[p].r = r; if(l == r) return ;
        int mid = (l + r) >> 1;
        build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    }
    void insertL(int p, int x, line cur) {
        if(tr[p].l == tr[p].r) return ;
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(x > mid) return insertL(p << 1 | 1, x, cur);
        tr[p].L.push_back(cur), insertL(p << 1, x, cur);
    }
    void insertR(int p, int x, line cur) {
        if(tr[p].l == tr[p].r) return ;
        int mid = (tr[p].l + tr[p].r) >> 1;
        if(x <= mid) return insertR(p << 1, x, cur);
        tr[p].R.push_back(cur), insertR(p << 1 | 1, x, cur);
    }
    void search(int p) {
        if(tr[p].l == tr[p].r) return ;
        search(p << 1), search(p << 1 | 1);
        if(tr[p].L.empty() || tr[p].R.empty()) return ;
        vector<line> lv, rv;
        for(auto x : tr[p].L) {
            while(lv.size() >= 2) {
                auto y = lv.back(), z = lv[lv.size() - 2];
                if((x.b - y.b) * (z.k - y.k) >= (y.b - z.b) * (y.k - x.k))
                    lv.pop_back();
                else break;
            }
            if(lv.empty() || lv.back().k != x.k) lv.push_back(x);
            else upd(lv.back().b, x.b);
        }
        for(auto x : tr[p].R) {
            while(rv.size() >= 2) {
                auto y = rv.back(), z = rv[rv.size() - 2];
                if((x.b - y.b) * (z.k - y.k) >= (y.b - z.b) * (y.k - x.k))
                    rv.pop_back();
                else break;
            }
            if(rv.empty() || rv.back().k != x.k) rv.push_back(x);
            else upd(rv.back().b, x.b);
        }
        for(auto &x : lv) x.k *= -1;
        for(auto &x : rv) x.k *= -1;
        int lenl = lv.size(), lenr = rv.size();
        for(int i = 0, j = 0; i < lenl && j < lenr; ) {
            upd(val[lv[i].k + rv[j].k], lv[i].b + rv[j].b);
            if(j + 1 == lenr) i++;
            else if(i + 1 == lenl) j++;
            else {
                int ki = lv[i + 1].k - lv[i].k, kj = rv[j + 1].k - rv[j].k;
                ll bi = lv[i + 1].b - lv[i].b, bj = rv[j + 1].b - rv[j].b;
                if(bi * kj >= bj * ki) i++; else j++;
            }
        }
    }
} Tr;

ll dp[N][4]; vector<int> vec[N]; int id[N];
void solve3() {
    ans3 = ans2;
    // Case 1
    fo(i, 1, n) vec[rb[i]].push_back(i);
    fo(i, 1, n) {
        fo(j, 1, 3) dp[i][j] = dp[i - 1][j];
        for(int x : vec[i]) fo(j, 1, 3)
            dp[i][j] = max(dp[i][j], dp[lb[x] - 1][j - 1] + arr[x].b);
    }
    ans3 = max(ans3, dp[n][3]);
    // Case 2
    fo(i, 1, n) ans3 = max(ans3, res[i] + max(pre[lb[i] - 1], suf[rb[i] + 1]));
    // Case 3
    reset(), dfs2(root);
    // Case 4
    Tr.build(1, 1, n); fo(i, 1, n) id[i] = i;
    sort(id + 1, id + n + 1, [&](int x, int y) {  return siz[x] < siz[y];  });
    fo(i, 1, n) {
        int x = id[i];
        Tr.insertL(1, rb[x], arr[x]), Tr.insertR(1, lb[x], arr[x]);
    }
    Tr.search(1), reset();
    fo(i, 1, n) insert(rt[0], 1, maxh, {-i, val[i]});
    fo(i, 1, n) {
        ll cur = query(rt[0], 1, maxh, a[i]) + arr[i].b;
        ans3 = max(ans3, cur);
    }
}

vector<ll> max_area(vector<int> H) {
    n = H.size();
    fo(i, 1, n) a[i] = H[i - 1], maxh = max(maxh, a[i]);
    build(), solve1(), solve2(), solve3();
    vector<ll> ans;
    ans.push_back(ans1);
    ans.push_back(ans2);
    ans.push_back(ans3);
    return ans;
}

#ifndef ONLINE_JUDGE
int main() {
    int N;
    std::vector<int> H;
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        int h;
        scanf("%d", &h);
        H.push_back(h);
    }
    std::vector<long long> ans = max_area(H);
    for(int i = 0; i < (int)ans.size(); i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}
#endif