#include <bits/stdc++.h>

using namespace std;

ifstream fin("psir.in");
ofstream fout("psir.out");

#define ui unsigned int

const ui NMAX = 2000 + 10;
const long long MOD = 1LL << 32;

vector < ui > aux;
ui x[NMAX];
ui i , N , j , ans , q;
ui dp[NMAX][NMAX];

int main()
{

fin >> N;

for (i = 1 ; i <= N ; ++i)
{
    fin >> x[i];
    aux.push_back(x[i]);
}

sort(aux.begin() , aux.end());
aux.resize(distance(aux.begin() , unique(aux.begin() , aux.end())));

for (i = 1 ; i <= N ; ++i)
x[i] = lower_bound(aux.begin() , aux.end() , x[i]) - aux.begin() + 1;

for (i = 1 ; i <= N ; ++i)
{
    for (j = 1 ; j < i ; ++j)
    {
        if (x[i] == x[j])
        {
            ans = (1LL + ans) % MOD;
            continue;
        }

        if (x[i] > x[j])
        {
            q = (1LL + dp[j][2000] - dp[j][x[i]]) % MOD;
            ans = (0LL + ans + q) % MOD;
            dp[i][x[j]] = (0LL + dp[i][x[j]] + q) % MOD;
        }
        else
        {
            q = (1LL + dp[j][x[i] - 1]) % MOD;
            ans = (0LL + ans + q) % MOD;
            dp[i][x[j]] = (0LL + dp[i][x[j]] + q) % MOD;
        }
    }

    for (j = 1 ; j <= 2000 ; ++j)
    dp[i][j] = (0LL + dp[i][j] + dp[i][j - 1]) % MOD;
}

fout << ans << '\n';

return 0;
}