#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+114;
struct info{
    int val;
    int cnt;
    info(int V=0,int C=1){
        val=V;
        cnt=C;
    }
    info operator+(info b){
        if(val==b.val){
            return info(val,cnt+b.cnt);
        }else if(val>b.val) return info(val,cnt);
        else return b;
    }
}tr[maxn<<2];
int a[maxn],lst[maxn],n;
int tot[maxn];
int tag[maxn<<2];
void pushup(int cur){
    tr[cur]=tr[cur<<1]+tr[cur<<1|1];
}
void pushdown(int cur){
    tr[cur<<1].val+=tag[cur];
    tag[cur<<1]+=tag[cur];
    tr[cur<<1|1].val+=tag[cur];
    tag[cur<<1|1]+=tag[cur];
    tag[cur]=0;
}
void add(int cur,int lt,int rt,int l,int r,int c){
    if(rt<l||r<lt) return ;
    if(l<=lt&&rt<=r){
        tr[cur].val+=c;
        tag[cur]+=c;
        return ;
    }
    pushdown(cur);
    int mid=(lt+rt)>>1;
    add(cur<<1,lt,mid,l,r,c);
    add(cur<<1|1,mid+1,rt,l,r,c);
    pushup(cur);
}
int lst1;
info ask(int cur,int lt,int rt,int l,int r){
    if(l<=lt&&rt<=r) return tr[cur];
    pushdown(cur);
    int mid=(lt+rt)>>1;
    if(l<=mid&&r>mid) return ask(cur<<1,lt,mid,l,r)+ask(cur<<1|1,mid+1,rt,l,r);
    else if(l<=mid) return ask(cur<<1,lt,mid,l,r);
    else return ask(cur<<1|1,mid+1,rt,l,r);
}
long long ans;
int stk[maxn],tp;
int colL=1;
int t[maxn];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        lst[i]=tot[a[i]];
        tot[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==1) lst1=i;
        while(a[stk[tp]]<a[i]&&tp>0){
            //区间 [stk[tp-1]+1,stk[tp]] 最大值由 a[skt[tp]] 变为 a[i]
            add(1,1,n,stk[tp-1]+1,stk[tp],a[stk[tp]]);
            tp--;
        }
        add(1,1,n,stk[tp]+1,i,-a[i]);
        stk[++tp]=i;
        add(1,1,n,1,i,1);
        while(t[a[i]]!=0){
            t[a[colL]]--;
            colL++;
        }
        t[a[i]]++;
        if(colL<=lst1){
            info res=ask(1,1,n,colL,lst1);
            if(res.val==0) ans+=res.cnt;
        }
    }
    cout<<ans<<'\n';
    return 0;
}