#include <cstdio>

#define file_in "psir.in"
#define file_out "psir.out"

#define nmax (1<<11)
#define mod (long long)(1<<16)*(long long)(1<<16)

int n,i,j,k;
long long ans;
long long v[nmax];
long long cnt[nmax][nmax];

int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	
	scanf("%d", &n);
	for (i=0;i<n;++i)
		 scanf("%lld", &v[i]);
	
	for (i=0;i<n;++i)
		 for (j=i+1;j<n;++j){
			 cnt[i][j]=1;
			 
			 if (v[i]<v[j])
			 for (k=0;k<i;++k)
				  cnt[i][j]+=(v[j]<v[k])*cnt[k][i];
			 if (v[j]<v[i])
			  for (k=0;k<i;++k)
				  cnt[i][j]+=(v[j]>v[k])*cnt[k][i];	 
			 ans+=cnt[i][j];
			 while(ans>mod)
				 ans-=mod;
		 }
		 
	printf("%lld\n", ans);

	return 0;
	
}