#include<bits/stdc++.h>
//#define HaojiaShi
#ifdef HaojiaShi
#define DX 16777220
#else
#define DX 167
#endif
using namespace std;
namespace file_read{
    namespace input_file_io{
        char ib[1<<25],*ip1=ib,*ip2=ib;
        inline char gc(){
#ifdef HaojiaShi
            return (ip1==ip2&&(ip2=(ip1=ib)+fread(ib,1,1<<24,stdin)),ip1==ip2?EOF:*ip1++);
#else
			return getchar();
#endif
        }
        inline int read(){
            int x=0,f=1;
            char c=gc();
            while(c<'0'||c>'9'){
            	if(c=='-')f=-1;
            	c=gc();
			}
            while(c>='0'&&c<='9'){
                x=(x<<3)+(x<<1)+(c-'0');
                c=gc();
            }
            return x*f;
        }
    };
    using namespace input_file_io;
};
using namespace file_read;
long long s1[DX+5],s2[DX+5];
int l1[DX+5],l2[DX+5];
void pushdown1(int l,int r,int o){
	if(!l1[o])return;
	int mid=(l+r)>>1;
	l1[o<<1]+=l1[o];
	l1[o<<1|1]+=l1[o];
	s1[o<<1]+=1ll*(mid-l+1)*l1[o];
	s1[o<<1|1]+=1ll*(r-mid)*l1[o];
	l1[o]=0;
}
void pushdown2(int l,int r,int o){
	if(!l2[o])return;
	int mid=(l+r)>>1;
	l2[o<<1]+=l2[o];
	l2[o<<1|1]+=l2[o];
	s2[o<<1]+=-1ll*(l+mid)*(mid-l+1)/2*l2[o];
	s2[o<<1|1]+=-1ll*(mid+1+r)*(r-mid)/2*l2[o];
	l2[o]=0;
}
void add1(int l,int r,int o,int ll,int rr,int x){
	if(l>=ll&&r<=rr){
		l1[o]+=x;
		s1[o]+=1ll*(r-l+1)*x;
		return;
	}
	pushdown1(l,r,o);
	int mid=(l+r)>>1;
	if(mid>=ll)add1(l,mid,o<<1,ll,rr,x);
	if(mid<rr)add1(mid+1,r,o<<1|1,ll,rr,x);
	s1[o]=s1[o<<1]+s1[o<<1|1];
}
void add2(int l,int r,int o,int ll,int rr,int x){
	if(l>=ll&&r<=rr){
		l2[o]+=x;
		s2[o]+=-1ll*(l+r)*(r-l+1)/2*x;
		return;
	}
	pushdown2(l,r,o);
	int mid=(l+r)>>1;
	if(mid>=ll)add2(l,mid,o<<1,ll,rr,x);
	if(mid<rr)add2(mid+1,r,o<<1|1,ll,rr,x);
	s2[o]=s2[o<<1]+s2[o<<1|1];
}
long long query1(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr)return s1[o];
	pushdown1(l,r,o);
	int mid=(l+r)>>1;
	long long ans=0;
	if(mid>=ll)ans+=query1(l,mid,o<<1,ll,rr);
	if(mid<rr)ans+=query1(mid+1,r,o<<1|1,ll,rr);
	return ans;
}
long long query2(int l,int r,int o,int ll,int rr){
	if(l>=ll&&r<=rr)return s2[o];
	pushdown2(l,r,o);
	int mid=(l+r)>>1;
	long long ans=0;
	if(mid>=ll)ans+=query2(l,mid,o<<1,ll,rr);
	if(mid<rr)ans+=query2(mid+1,r,o<<1|1,ll,rr);
	return ans;
}
int a[3000005];
vector<int>g[3000005];
int LL,RR,PY;
long long ans;
void add(int l,int r){
	if(l>r)return;
	l+=PY,r+=PY;
	if(LL<l)ans+=(r-l+1)*query1(LL,RR,1,LL,l-1);
	ans+=query2(LL,RR,1,l,r);
	ans+=r*query1(LL,RR,1,l,r);
	add1(LL,RR,1,l,r,1);
	add2(LL,RR,1,l,r,1);
}
void del(int l,int r){
	if(l>r)return;
	l+=PY,r+=PY;
	add1(LL,RR,1,l,r,-1);
	add2(LL,RR,1,l,r,-1);
}
int main(){
	int n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		g[a[i]].emplace_back(i);
	}
	PY=n+1,LL=1,RR=n+n+1;
	ans=0;
	for(int i=1;i<=n;++i)if(g[i].size()){
		int s;
		g[i].emplace_back(n+1);
		s=0;
		add(s=(1-g[i][0]),0);
		for(int j=0;j<(signed)g[i].size()-1;++j){
			int L=g[i][j],R=g[i][j+1];
			++s;
			add(s,s);
			if(L+1<R){
				add(s-(R-L-1),s-1);
				s-=R-L-1;
			}
		}
		s=0;
		del(s=(1-g[i][0]),0);
		for(int j=0;j<(signed)g[i].size()-1;++j){
			int L=g[i][j],R=g[i][j+1];
			++s;
			del(s,s);
			if(L+1<R){
				del(s-(R-L-1),s-1);
				s-=R-L-1;
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}