#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define MAXN 2048
#define MAXT 4096

int N;
vector<int> x, sorted;

unsigned NR[MAXN][MAXN];			//NR[i][j] = numarul de p-subsiruri cu ultimul element j si penultimul element i
						//NR[i][j] = 1 + suma NR[k][i], k < i si (x[j] - x[k]) * (x[j] - x[i]) < 0
long long aint[MAXT];


inline long long query( int n, int l, int r, int vl, int vr )
{
	if (vl <= l && r <= vr)
		return aint[n];

	int m = (l + r) >> 1, lc = (n << 1), rc = lc + 1;
	long long REZ = 0;
	if (vl <= m)
		REZ += query( lc, l, m, vl, vr );
	if (vr > m)
		REZ += query( rc, m + 1, r, vl, vr );
	return REZ & 0xFFFFFFFF;
}

inline void add( int n, int l, int r, int poz, int val )
{
	if (l == r)
	{
		aint[n] += val;
		aint[n] &= 0xFFFFFFFF;
		return;
	}

	int m = (l + r) >> 1, lc = (n << 1), rc = lc + 1;
	if (poz <= m)
		add( lc, l, m, poz, val );
	else
		add( rc, m + 1, r, poz, val );

	aint[n] = aint[lc] + aint[rc];
	aint[n] &= 0xFFFFFFFF;
}

int main()
{
	freopen("psir.in", "rt", stdin);
	freopen("psir.out", "wt", stdout);

	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		int val;
		scanf("%d", &val);
		x.push_back(val);
	}

	sorted = x;
	sort( sorted.begin(), sorted.end() );
	sorted.resize( unique(sorted.begin(), sorted.end()) - sorted.begin() );

	for (int i = 0; i < N; i++)
		x[i] = lower_bound( sorted.begin(), sorted.end(), x[i] ) - sorted.begin() + 1;

	unsigned TOT = 0;
	for (int i = 0; i < N; i++)			//penultimul element din p-sir
	{
		memset( aint, 0, sizeof(aint) );
		for (int k = 0; k < i; k++)
			add( 1, 1, N, x[k], NR[k][i] );

		for (int j = i + 1; j < N; j++)		//ultimul element din p-sir
		{
			NR[i][j] = 1;

			if (x[i] < x[j] && x[j] + 1 <= N)
				NR[i][j] = ( query(1, 1, N, x[j] + 1, N) + NR[i][j] ) & 0xFFFFFFFF;
			if (x[i] > x[j] && x[j] - 1 >= 1)
				NR[i][j] = ( query(1, 1, N, 1, x[j] - 1) + NR[i][j] ) & 0xFFFFFFFF;

			TOT = ((long long)TOT + NR[i][j]) & 0xFFFFFFFF;
		}
	}
	printf("%u\n", TOT);

	return 0;
}