#include <cstdio>
#include <cstdlib>

#define I_F "queueb.in"
#define O_F "queueb.out"

const long MAXn=50000;

struct treap
{
	long x,y,z;
	treap *f, *l, *r;
};

treap pool[MAXn];
treap *ph=pool;
long n;
long s[MAXn];
long a[MAXn], b[MAXn];
long long ans=0;
treap *root=NULL;

void Input();
inline void Lefturn(treap*);
inline void Righturn(treap*);
long Insert(const long&);
inline void Clear();
void Search();
void Output();

int main()
{
	Input();
	Search();
	Output();
	return 0;
}

void Input()
{
	freopen(I_F,"r",stdin);
	scanf("%ld",&n);
	for (long i=0; i<n; ++i)
		scanf("%ld",&s[i]);
}

inline void Lefturn(treap *p)
{
	treap *f=p->f;
	treap *a=p->l, *b=p->r, *c=f->r;
	if (f->f==NULL)
		root=p;
	else
		if (f->f->l==f)
			f->f->l=p;
		else
			f->f->r=p;
	p->f=f->f;
	f->f=p;
	p->r=f;
	f->l=b;
	if (b!=NULL)
		b->f=f;
	f->z=1+((b!=NULL)?b->z:0)+((c!=NULL)?c->z:0);
	p->z=1+((a!=NULL)?a->z:0)+f->z;
}

inline void Righturn(treap *f)
{
	treap *p=f->f;
	treap *a=p->l, *b=f->l, *c=f->r;
	if (p->f==NULL)
		root=f;
	else
		if (p->f->l==p)
			p->f->l=f;
		else
			p->f->r=f;
	f->f=p->f;
	p->f=f;
	f->l=p;
	p->r=b;
	if (b!=NULL)
		b->f=p;
	p->z=1+((a!=NULL)?a->z:0)+((b!=NULL)?b->z:0);
	f->z=1+((c!=NULL)?c->z:0)+p->z;
}

long Insert(const long &x)
{
	if (root==NULL)
	{
		root=ph++;
		root->x=s[x];
		root->y=rand()%MAXn;
		root->z=1;
		root->f=root->l=root->r=NULL;
		return 0;
	}
	treap *i=root;
	while (true)
		if (s[x]==i->x)
		{
			for (treap *j=i; j!=NULL; j=j->f)
				++j->z;
			break;
		}
		else
			if (s[x]<i->x)
				if (i->l!=NULL)
					i=i->l;
				else
				{
					i->l=ph++;
					i->l->f=i;
					i=i->l;
					i->l=i->r=NULL;
					i->x=s[x];
					i->y=rand()%MAXn;
					i->z=1;
					for (treap *j=i->f; j!=NULL; j=j->f)
						++j->z;
					break;
				}
			else
				if (i->r!=NULL)
					i=i->r;
				else
				{
					i->r=ph++;
					i->r->f=i;
					i=i->r;
					i->l=i->r=NULL;
					i->x=s[x];
					i->y=rand()%MAXn;
					i->z=1;
					for (treap *j=i->f; j!=NULL; j=j->f)
						++j->z;
					break;
				}
	while (i->f!=NULL && i->z>i->f->z)
		if (i==i->f->l)
			Lefturn(i);
		else
			Righturn(i);
	long re=(i->l!=NULL)?i->l->z:0;
	while (i->f!=NULL)
	{
		if (i==i->f->r)
			re+=(i->f->z-i->z);
		i=i->f;
	}
	return re;
}

inline void Clear()
{
	root=NULL;
	ph=pool;
}

void Search()
{
	for (long i=0; i<n; ++i)
		a[i]=Insert(i);
	Clear();
	for (long i=n-1; i>=0; --i)
		b[i]=Insert(i);
	for (long i=0; i<n; ++i)
		ans+=a[i]*b[i];
}

void Output()
{
	freopen(O_F,"w",stdout);
	printf("%lld\n",ans);
}