#include <stdio.h>
#include <set>

using namespace std;

#define aduna(x, y) (((x += y) >= MOD) ? (x -= MOD) : 0)
#define MOD ((ll)1<<32)
#define ll long long
#define NMax 1005 // de schimbat in 2005!!!!!!!!

int N, v[NMax], norm[NMax], h = 0;
ll D[NMax][NMax], SUM[NMax][NMax], cnt = 0;
set<int> A;

int BS(int X)
{
    int l, r, m;

    l = 1; r = h;
    while (l <= r)
    {
        m = (l + r) / 2;
        if (norm[m] < X) l = m+1;
        else if (norm[m] > X) r = m-1;
        else return m;
    }

    return -1; // should never arrive here
}

int main(void)
{
    int i, j, x;
    set<int>::iterator it;
    
    freopen("psir.in", "r", stdin);
    freopen("psir.out", "w", stdout);

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

    for (i = 1; i <= N; i++)
        A.insert(v[i]);

    for (it = A.begin(); it != A.end(); it++)
        norm[++h] = *it;

    for (i = 1; i <= N; i++)
        v[i] = BS(v[i]);

    for (i = 1; i <= N; i++)
    {
        for (j = 1; j < i; j++)
            aduna(D[v[j]][v[i]], 1);
        
        for (j = 1; j < v[i]; j++)
        {
            x = SUM[N][j] - SUM[v[i]][j];
            if (x < 0) x += MOD;
            
            aduna(D[j][v[i]], x);            
        }
        
        for (j = v[i]+1; j <= N; j++)
            aduna(D[j][v[i]], SUM[v[i]-1][j]);

        // actualizam
        for (j = 1; j <= N; j++)
        {
            SUM[j][v[i]] = SUM[j-1][v[i]] + D[j][v[i]];
            if (SUM[j][v[i]] >= MOD)
                SUM[j][v[i]] -= MOD;
        }
    }

    for (i = 1; i <= N; i++)
        for (j = 1; j <= N; j++)
            aduna(cnt, D[i][j]);


    printf("%u\n", cnt % MOD);


    return 0;
}