#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxN 1002
#define mod 4294967296
using namespace std;
int n, i, j;
unsigned int v[maxN], dp[maxN][maxN], Dp[maxN][maxN], sol;
struct vect
{
    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("%d", &n);
    for (i = 1; i <= n; ++ i)
    {
        scanf("%d", &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;
    }
    for (i = 1; i <= n; ++ i)
    {
        dp[i][v[i]] = Dp[i][v[i]] = 1;
        for (j = i - 1; j >= 1; -- j)
            if (v[i] < v[j])
        {
            dp[i][v[j]] = (dp[i][v[j]] + Dp[j][v[i] - 1]) % mod;
            Dp[i][v[j]] = (Dp[i][v[j]] + Dp[j][v[i] - 1]) % mod;
        }
        else if (v[i] > v[j])
        {
            dp[i][v[j]] = (dp[i][v[j]] + dp[j][v[i] + 1]) % mod;
            Dp[i][v[j]] = (Dp[i][v[j]] + dp[j][v[i] + 1]) % mod;
        }
        else
            sol = (sol + 2) % mod;
        for (j = 1; j <= n; ++ j)
        {
            Dp[i][j] = (Dp[i][j - 1] + Dp[i][j]) % mod;
            dp[i][n - j + 1] = (dp[i][n - j + 2] + dp[i][j]) % mod;
        }
        sol += dp[i][n];
    }

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