#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
int a[N],n,p=-1;
map<int,pair<vector<int>,vector<int>>> b;
int tr[4*N];
void build(int x,int l,int r){
    if (l==r){
        tr[x]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid);
    build(x<<1|1,mid+1,r);
    tr[x]=min(tr[x<<1],tr[x<<1|1]);
}
int query(int x,int l,int r,int L,int R){
    if (L<=l && r<=R) return tr[x];
    int mid=(l+r)>>1;
    if (R<=mid) return query(x<<1,l,mid,L,R);
    if (L>mid) return query(x<<1|1,mid+1,r,L,R);
    return min(query(x<<1,l,mid,L,R),query(x<<1|1,mid+1,r,L,R));
}
void modify(int x,int l,int r,int p,int v){
    if (l==r){
        tr[x]=v;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) modify(x<<1,l,mid,p,v);
    else modify(x<<1|1,mid+1,r,p,v);
    tr[x]=min(tr[x<<1],tr[x<<1|1]);
}
set<int> s;
int main(){
    // freopen("a.in","r",stdin);
    scanf("%d",&n);
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        if (p==-1 || a[i]>a[p]) p=i;
        b[a[i]].first.emplace_back(i);
    }
    for (int i=1,mx=0;i<=p;++i){
        mx=max(mx,a[i]);
        b[mx].second.emplace_back(i);
    }
    for (int i=n,mx=0;i>p;--i){
        mx=max(mx,a[i]);
        b[mx].second.emplace_back(i);
    }
    build(1,1,n);
    ll ans=0;
    for (auto it=b.begin();it!=b.end();++it){
        auto obj=*it;
        ll h=obj.first;
        for (auto x:obj.second.first) s.emplace(x);
        for (auto x:obj.second.second) s.erase(x),modify(1,1,n,x,1e9);
        if (next(it)==b.end()) break;
        ll v=next(it)->first;
        if (!s.size()) continue;
        ll x=query(1,1,n,1,*s.begin()-1),y=query(1,1,n,*prev(s.end())+1,n);
        if (s.size()==1) ans+=(v-h)*(x+y)+(h+v-1)*(v-h)/2;
        else ans+=(v-h)*(max(x,y)+2*min(x,y)+1+2*(s.size()-2))+(3+3*(s.size()-2))*(h+v-1)*(v-h)/2;
    }
    printf("%lld\n",ans);
    return 0;
}