#include <stdio.h>

#define maxN 2010

struct st{short x;unsigned k;operator int()const{return x;}};

unsigned res;
int n,vec[maxN],acc[maxN],an=1;
st*din[maxN];

int bs(st*v,int n,int x){
	int st=0,en=n-1,m;
	while(st<en){
		m=st+en>>1;
		if(x<=vec[v[m]])en=m;else st=m+1;
	}
	while(en>=0 && vec[v[en]]>=x)en--;
	return en;
}

int bs2(st*v,int n,int x){if(!n)return -1;
	int st=0,en=n-1,m;
	while(st<en){
		m=st+en>>1;
		if(x<=vec[v[m]])en=m;else st=m+1;
	}
	while(st<n-1 && vec[v[st]]==x)st++;
	while(st>=0 && vec[v[st]]>x)st--;
	
	return st;
}

void ins(int p){
	int i,j,x=vec[p];
	for(i=0;i<an && vec[acc[i]]<=x ;i++);
	for(j=an++;j>i;j--)acc[j]=acc[j-1];
	acc[i]=p;
}
void inputFunc(){FILE*fi=fopen("psir.in","r");fscanf(fi,"%d",&n);for(int i=0;i<n;i++)fscanf(fi,"%d",vec+i);fclose(fi);}
void outputFunc(){FILE*fi=fopen("psir.out","w");fprintf(fi,"%u",res);fclose(fi);}

int main(){
	inputFunc();

	for(int i=1;i<n;i++){
		int cur=vec[i];din[i]=new st[i];

		for(int g=0,j=acc[0];g<i;j=acc[++g]){ //mergem pe acc
			int q=bs(din[j],j,cur),q2=bs2(din[j],j,cur);
			din[i][g].k=0,din[i][g].x=j;
			
			if(cur<vec[j]){
				if(q>=0)din[i][g].k=din[j][q].k;
			}else
			if(cur>vec[j]){
				if(j)din[i][g].k=din[j][j-1].k;
				if(q2>=0)din[i][g].k-=din[j][q2].k;
			}
			
			
			din[i][g].k++;
			if(g)din[i][g].k+=din[i][g-1].k;
			
		}
		
		res+=din[i][i-1].k;
		ins(i);
	}
	
	
	outputFunc();
	return 0;
}