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

#define MAX 2048
#define ll long long

using namespace std;

ll n, rez;
ll x[MAX], v[MAX];
ll sum[MAX];
ll sol[MAX][MAX];

int main()
{
	freopen("psir.in", "r", stdin);
	freopen("psir.out", "w", stdout);

	scanf("%d", &n);

	for (int i = 1; i <= n; v[x[i]], i++)
		scanf("%d", &x[i]);

	sort(v + 1, v + 1 + n);

	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (v[j] == x[i])
				x[i] = j;

	ll restRez = ((ll) 1 << 32);
	for (int i = 1; i <= n; i++)
	{
		memset(sum, 0, sizeof(sum));

		for (int j = 1; j < i; j++)
			sum[x[j]] = (sum[x[j]] + sol[j][i]) % restRez;

		for (int j = 1; j <= x[i]; j++)
			sum[j] = (sum[j] + sum[j - 1]) % restRez;
		for (int j = n; j >= x[i]; j--)
			sum[j] = (sum[j] + sum[j + 1]) % restRez;

		for (int j = i + 1; j <= n; j++)
		{
			sol[i][j] = 1;
			if (x[j] < x[i])
				sol[i][j] += sum[x[j] - 1];
			else if (x[j] > x[i])
				sol[i][j] += sum[x[j] + 1];

			sol[i][j] %= restRez;

			rez = (rez + sol[i][j]) % restRez; 
		}
	}

	printf("%lld\n", rez);

	fclose(stdin);
	fclose(stdout);
	return 0;
}