const int inf = 1e9+7;
#define data _data
struct data{
    ll mx, mx_cnt, mx2, sum;

    constexpr data(ll m):mx(m), mx_cnt(1), mx2(-inf), sum(m) {}
    constexpr data(ll mx, ll mx_cnt, ll mx2, ll sum):mx(mx), mx_cnt(mx_cnt), mx2(mx2), sum(sum) {}
};
data join(data A, data B)
{
    if(A.mx == B.mx)
        return {A.mx, A.mx_cnt+B.mx_cnt, max(A.mx2, B.mx2), A.sum+B.sum};
    if(A.mx < B.mx) swap(A, B);
    return {A.mx, A.mx_cnt, max(A.mx2, B.mx), A.sum+B.sum};
}
using Seg = vector<data>;

void init(Seg& seg, int i, int s, int e, ll* A)
{
    if(s == e) { seg[i] = A[s]; return; }
    int mid  = (s+e)/2;
    init(seg, i*2, s, mid, A); init(seg, i*2+1, mid+1, e, A);
    seg[i] = join(seg[i*2], seg[i*2+1]);
}

void prop(Seg& seg, int i, int s, int e)
{
    if(s == e) return;
    
    for(auto t : {i*2, i*2+1}) {
        if(seg[t].mx > seg[i].mx) {
            seg[t].sum -= seg[t].mx_cnt * (seg[t].mx - seg[i].mx);
            seg[t].mx = seg[i].mx;
        }
    }
}

void update(Seg& seg, int i, int s, int e, int a, int b, ll v)
{
    prop(seg, i, s, e);
    if(e<a || b<s || seg[i].mx <= v) return;
    if(a<=s && e<=b && seg[i].mx2 < v)
    {
        seg[i].sum -= seg[i].mx_cnt * (seg[i].mx - v);
        seg[i].mx = v;
        prop(seg, i, s, e);
        return;
    }

    int mid = (s+e)/2;
    update(seg, i*2, s, mid, a, b, v);
    update(seg, i*2+1, mid+1, e, a, b, v);

    seg[i] = join(seg[i*2], seg[i*2+1]);
}

ll querymax(Seg& seg, int i, int s, int e, int a, int b)
{
    prop(seg, i, s, e);
    if(e<a || b<s) return -inf;
    if(a<=s && e<=b) return seg[i].mx;

    int mid = (s+e)/2;
    return max(querymax(seg, i*2, s, mid, a, b), querymax(seg, i*2+1, mid+1, e, a, b));
}

ll querysum(Seg& seg, int i, int s, int e, int a, int b)
{
    prop(seg, i, s, e);
    if(e<a || b<s) return 0;
    if(a<=s && e<=b) return seg[i].sum;

    int mid = (s+e)/2;
    return querysum(seg, i*2, s, mid, a, b)+querysum(seg, i*2+1, mid+1, e, a, b);
}

const int N = 1e6+7;
ll A[N];

getint(n); get A;
Seg s(4*n, 0); init(s, 1, 1, n, A);

// A[i] = min(A[i], x) for l <= i <= r
update(s, 1, 1, n, l, r, x); 
// summation query, max query
querysum(s, 1, 1, n, l, r), querymax(s, 1, 1, n, l, r);