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

using namespace std;

#define nm 2048

const long long mod = (long long)65536 * 65536;//4294967296

int n, a[nm], p[nm], v[nm];
unsigned int c[nm], s[nm][nm], sol;

int comp(int first, int second)
{
	return a[first] < a[second];
}

int main()
{
	int i, j;
	long long t;

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

	scanf("%d", &n);

	for (i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		p[i] = i;
	}

	sort(p + 1, p + n + 1, comp);

	v[p[1]] = 1;

	for (i = 2, j = 1; i <= n; ++i)
	{
		if (a[p[i]] != a[p[i - 1]])
			++j;

        v[p[i]] = j;
	}

    for (i = 2; i <= n; ++i)
	{
    	for (j = 1; j <= i - 1; ++j)
		{
			if (v[i] < v[j])
	        	t = (long long)c[v[j]] + (long long)s[j][v[i] - 1] + 1;
            else if (v[i] > v[j])
			{
				t = (long long)s[j][n] - (long long)s[j][v[i]];

				if (t < 0)
					t += mod;
					
				t = (long long)c[v[j]] + (long long)t + 1;
            }
            else
				t = (long long)c[v[j]] + 1;

			if (t >= mod)
				c[v[j]] = t - mod;
            else
            	c[v[j]] = t;
		}
		
		for (j = 1; j <= n; ++j)
		{
        	t = (long long)s[i][j - 1] + c[j];

			if (t >= mod)
				s[i][j] = t - mod;
            else
				s[i][j] = t;
        }

        for (j = 1; j <= n; ++j)
			c[j] = 0;
	}
	
    for (i = 1; i <= n; ++i)
	{
		t = (long long)sol + s[i][n];

		if (t >= mod)
			sol = t - mod;
        else
			sol = t;
    }

    printf("%u\n", sol);

	return 0;
}