#include <cstdio>
#define lm 2010

struct poz
{
	int v, p;
} c[lm];

int cmp(poz a, poz b)
{
	return a.v<b.v;
}

int v[lm], n;
unsigned int a[lm][lm];

int search(int s, int d, int l, int x)
{
	int m, r=0;
	while (s<=d)
	{
		m=(s+d)/2;
		if (a[l][m]>x) d=m-1; else 
		{
			s=m+1;
			r=m;
		}
	}
	return r;
}

int main()
{
	freopen("psir.in","r",stdin);
	freopen("psir.out","w",stdout);
	scanf("%d",&n);
	int i, j, p, k, y, ok;
	for (i=1; i<=n; i++) scanf("%d",&v[i]);
	for (i=2; i<=n; i++)
	{
		ok=0;
		for (j=1; j<=i-2; j++)
			if (c[j].v>=v[i-1])
			{
				for (y=i-1; y>j; y--)
				{
					c[y].v=c[y-1].v;
					c[y].p=c[y-1].p;
				}
				c[j].v=v[i-1];
				c[j].p=i-1;
				ok=1;
				break;
			}
		if (!ok)
		{
			c[i-1].v=v[i-1];
			c[i-1].p=i-1;
		}
		for (j=1; j<i; j++) a[i][j]=c[j].v;
		for (j=1; j<i; j++)
		{
			k=c[j].p;
			if (v[i]<v[k])
			{
				p=search(1,k-1,k,v[i]-1);
				a[n-i+1][n-i+1+j]=a[n-i+1][n-i+1+j-1]+a[n-k+1][n-k+1+p]+1;
			} else
			if (v[i]>v[k])
			{
				p=search(1,k-1,k,v[i]);
				a[n-i+1][n-i+1+j]=a[n-i+1][n-i+1+j-1]+(a[n-k+1][n-k+1+k-1]-a[n-k+1][n-k+1+p])+1;
			} else a[n-i+1][n-i+1+j]=a[n-i+1][n-i+1+j-1]+1;
		}
	}
	unsigned int r=0;
	for (i=1; i<n; i++) r=r+a[i][n];
	printf("%u",r);
}