#include <bits/stdc++.h>

using namespace std;

const int N=2000;
static uint32_t mod=(1U<<32)-1;

void add(uint32_t &a, uint32_t b) {
	a=(1LL*a+b)&mod;
}

int n,a[N+1];
uint32_t dp[N+1][N+1];

void read(){
	cin>>n;
	vector <int> auxa;
	for(int i=1;i<=n;++i)cin>>a[i], auxa.push_back(a[i]);
	sort(auxa.begin(),auxa.end()), auxa.resize(unique(begin(auxa), end(auxa)) - begin(auxa));
	for(int i=1;i<=n;++i)a[i]=lower_bound(begin(auxa),end(auxa),a[i])-begin(auxa)+1;

}

void solve(){
	uint32_t sol=0;
	for(int i=1;i<=n;++i){
	   for(int j=1;j<i; j ++){
	   	  uint32_t tmp=1;
	   	  if(a[i]>a[j])
			add(tmp,dp[j][n]-dp[j][a[i]]);
	   	  else if(a[i]<a[j])tmp += dp[j][a[i] - 1];
	   	  add(dp[i][a[j]],tmp);
	   	  add(sol,tmp);
	   }
	   for(int x=2;x<=n;++x)add(dp[i][x],dp[i][x-1]);
	}
	cout<<sol;
	}


int main() {
	freopen("psir.in","r",stdin);
	freopen("psir.out","w",stdout);
	read();
	solve();
	return 0;
}