#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 2002
#define mod 4294967296LL
using namespace std;
unsigned int n, m, i, j, v[maxN], dp[maxN][maxN], sol;
struct vect
{
    unsigned int x;
    int y;
}a[maxN];
int cmp(const vect a, const vect b)
{
    return a.x < b.x;
}
void read()
{
    freopen("psir.in", "r", stdin);
    scanf("%u", &n);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%u", &a[i].x);
        a[i].y = i;
    }
}
void solve()
{
    sort(a + 1, a + n + 1, cmp);
    for (i = 1; i <= n; ++ i)
    {
        if (a[i].x != a[i - 1].x)
            ++ j;
        v[a[i].y] = j;
    }
    m = j;
    for (i = 1; i < n; ++ i)
        for (j = i + 1; j <= n; ++ j)
            ++ dp[j][v[i]];

    for (i = 1; i <= n; ++ i)
    {
        for (j = i - 1; j >= 1; -- j)
            if (v[i] < v[j])
                dp[i][v[j]] = (dp[i][v[j]] + dp[j][1] - dp[j][v[i]] + mod) % mod;
        else if (v[i] > v[j])
            dp[i][v[j]] = (dp[i][v[j]] + dp[j][v[i] + 1]) % mod;

        for (j = m; j >= 1; -- j)
            dp[i][j] = (dp[i][j + 1] + dp[i][j]) % mod;

        sol = (sol + dp[i][1]) % mod;
    }

}
void write()
{
    freopen("psir.out", "w", stdout);
    printf("%u\n", sol);
}
int main()
{
    read();
    solve();
    write();
    return 0;
}