#include <fstream>

#include <algorithm>
#include <utility>
#define x first
#define y second

using namespace std;

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

typedef pair <int, int> pii;
const int nmax = 2000;
const int maxint = (1 << 30) - 1 + (1 << 30);
const int64_t mod = (1ll << 32);

int n, a[nmax + 2], nvs;
pii norm[nmax + 2];

uint32_t dp[nmax + 2][nmax + 2], ways = 0, prefsum;
///dp[i][j] = nr de subsiruri cu ultimul element pe a[i], iar penultiuml j

uint32_t add(int64_t x, int64_t y){
    return (int64_t(x) + int64_t(y)) % mod;
}

int main(){

    in>>n;
    for(int i = 1; i <= n; i++){
        in>>a[i], norm[i] = make_pair(a[i], i);
    }

    /// ---> Normalize values <--- ///
    sort(norm + 1, norm + 1 + n);
    norm[0] = make_pair(-maxint, -maxint);

    for(int i = 1; i <= n; i++){
        nvs += (norm[i].x != norm[i - 1].x);
        a[norm[i].y] = nvs;
    }

    for(int i = 1; i <= n; i++){
        for(int a1 = 1; a1 <= i - 1; a1++){
            dp[i][a[a1]] = add(dp[i][a[a1]], uint32_t(1)); ///new subsir

            if(a[i] == a[a1]){ continue; }

            if(a[i] < a[a1]){ ///value = {1, 2, ..., a[i] - 1}
                dp[i][a[a1]] = add(dp[i][a[a1]], dp[a1][a[i] - 1]);
            }else{
                int64_t summ = (int64_t(dp[a1][n]) - int64_t(dp[a1][a[i]]) + mod);
                dp[i][a[a1]] = add(dp[i][a[a1]], summ);
            }
        }

        prefsum = 0;
        for(int value = 1; value <= n; value++){
            ways = add(ways, dp[i][value]);
            prefsum = add(prefsum, dp[i][value]);

            dp[i][value] = prefsum;
        }
    }

    out<<ways<<"\n";

    return 0;
}