#include <stdio.h>
#include <algorithm>
#define Nmax 2000+2
#define LL long long
using namespace std;

int v[Nmax],pe_poz[Nmax],S[Nmax];
int a[Nmax][Nmax];
int N;
LL rez,Mod;

int main(){
	int i,j,eg,mm,MM,t;
	Mod=(LL)1<<32;
	freopen("psir.in","r",stdin);
	freopen("psir.out","w",stdout);
	scanf("%d",&N);
	for(i=1;i<=N;++i) scanf("%d",&v[i]);
	if( v[1]<v[2] ) pe_poz[1]=1, pe_poz[2]=2;
	else pe_poz[1]=2, pe_poz[2]=1;
	
	a[2][1]=1;
	for(i=3;i<=N;++i){ // elem a[i]
		eg=mm=MM=0;
		for(j=1;j<i;++j){
			a[i][j]=1; // de cate 2 i cu j
			
			if( v[j] == v[i] ){
				++eg;
			}else
			if( v[j] > v[i] ){
				++MM;
				a[i][j]=((LL)a[i][j]+a[j][mm])%Mod; // adun (j cu mai mic)
			}
			else{
				++mm;
				if( mm+eg<j-1)
					a[i][j]=((LL)a[i][j]+a[j][j-1]-a[j][mm+eg])%Mod; // adun (j cu mai mare)
			}
		}
		
		for(j=1;j<i;++j)
			S[j]=((LL)S[j-1]+a[i][pe_poz[j]])%Mod;
		for(j=1;j<i;++j)
			a[i][j]=S[j];
		for(j=1;j<i;++j)
			if( v[pe_poz[j]] > v[i] ) break;
		for(t=i;t>j;--t) pe_poz[t]=pe_poz[t-1];
		pe_poz[j]=i;
	}
	
	for(i=1;i<=N;++i)
		rez=((LL)rez+a[i][i-1])%Mod;
	printf("%d\n",rez);
	fclose(stdin); fclose(stdout);
	return 0;
}