#include <stdio.h>
#include <algorithm>

using namespace std;

const char iname[] = "psir.in";
const char oname[] = "psir.out";

#define MAX_N  2000
#define Modulo (0xFFFFFFFF)

typedef unsigned int i32;

int n, P[MAX_N], m, Q[MAX_N], F[MAX_N];

i32 A[MAX_N][MAX_N];


void read_in(void)
{
	FILE *fi = fopen(iname, "r");

	fscanf(fi, "%d", &n);
	
	for (int i = 0; i < n; ++ i)
		fscanf(fi, "%d", &P[i]), Q[i] = P[i];

	sort(Q, Q + n);

	for (int i = m = 0; i < n; ++ i) {
		if (i == 0)
			m ++;
		else if (i > 0)
			if (Q[m - 1] != Q[i])
				Q[m ++] = Q[i];
	}
}

i32 query(i32 A[], int lo, int hi)
{
	if (hi < lo)  
		return 0;

	i32 sum;

	if (lo > 0) {
		if (A[hi] >= A[lo - 1])
			sum = A[hi] - A[lo - 1];
		else
			sum = (Modulo - A[lo - 1] + A[hi]) & Modulo;
	} else if (lo == 0)
		sum = A[hi];

	return sum;
}

i32 f(void)
{
	i32 ans = 0;

	for (int i = 0; i < n; ++ i) {
		for (int j = 0; j < m; ++ j)
			if (P[i] == Q[j])	  F[i] = j;
	}
	for (int i = 1; i < n; ++ i) {
		for (int j = 0; j < i; ++ j) {
			i32 cnt;
			if (P[j] < P[i])
				cnt = query(A[j], F[i] + 1, m - 1);
			else if (P[j] > P[i])
				cnt = query(A[j], 0, F[i] - 1);
			else
				cnt = 0;
			A[i][F[j]] = (A[i][F[j]] + (cnt + 1)) & Modulo;
			ans = (ans + (cnt + 1)) & Modulo;
		}
		for (int j = 1; j < m; ++ j)
			A[i][j] = (A[i][j] + A[i][j - 1]) & Modulo;
	}

	return ans;
}

int main(void)
{
	read_in();    	
	
	fprintf(fopen(oname, "w"), "%u", f());

	return 0;
}