#include <bits/stdc++.h>

using namespace std;
int n;
int a[200005];
int nxt[200005];
int dd[200005];
long long val;
long long ans=0;
int now[200005];
set<int>s;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1; i<=n; i++)cin>>a[i];
    for(int i=1; i<=n+1; i++)dd[i]=n+1;
    for(int i=n; i>=1; i--)nxt[i]=dd[a[i]],dd[a[i]]=i;
    int maxx=0;
    for(int i=1; i<=n+1; i++) {
        if(dd[i]>maxx) {
            maxx=dd[i];
            s.insert(i);
        }
        now[i]=dd[i];

    }
    int pre=1;
    for(auto it=s.begin(); it!=s.end(); it++) {
        val+=(*it)*(now[*it]-pre);
        pre=now[*it];
    }
    ans=val;
    for(int i=1; i<=n-1; i++) {
        if(now[*s.begin()]>i)
            val-=(*s.begin());
        auto it=s.lower_bound(a[i]);
        if(it==s.end()) {
            ans+=val;
            continue;
        }
        if(it!=s.begin()&&now[*prev(it)]>nxt[i]){ans+=val;continue;}
        if(*it==a[i]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*next(it);
            if(now[a[i]]>=ll)
                val-=a[i]*(now[a[i]]-ll);
            val-=r*(now[r]-now[a[i]]);
            val+=r*(now[r]-ll);
            s.erase(it++);
        }
        now[a[i]]=nxt[i];
        while(next(it)!=s.end()&&now[a[i]]>now[*it]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*next(it);
            val-=(*it)*(now[*it]-ll);
            val-=r*(now[r]-now[*it]);
            val+=r*(now[r]-ll);
            s.erase(it++);
        }
        if(*it<a[i]) {
            ans+=val;
            continue;
        }
        if(now[a[i]]>=now[*it]) {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            val-=(*it)*(now[*it]-ll);
            val+=a[i]*(now[a[i]]-ll);
            s.erase(it);
        } else {
            int ll;
            int r;
            if(it==s.begin())ll=i+1;
            else ll=now[*prev(it)];
            r=*it;
            val-=(*it)*(now[*it]-ll);
            val+=a[i]*(now[a[i]]-ll);
            val+=r*(now[r]-now[a[i]]);
        }
        s.insert(a[i]);
        ans+=val;
        //cout<<i<<" "<<val<<'\n';
    }
    cout<<ans;
    return 0;
}