#include <fstream>
#include <algorithm>
#include <cstring>
#define DIM 2010
#define MOD (1LL<<32)
using namespace std;

ifstream fin ("psir.in");
ofstream fout ("psir.out");
int v[DIM],w[DIM];
int n,i,j,k;
long long sol,d[DIM][DIM];
int cautare_binara (int v[], int n, int val){
    int st = 1, dr = n;
    while (st <= dr){
        int mid = (st+dr)/2;
        if (v[mid] == val)
            return mid;
        if (v[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }}

int main (){

    fin>>n;
    for (i=1;i<=n;i++){
        fin>>v[i];
        w[i] = v[i];
    }
    sort (w+1,w+n+1);
    k = 1;
    for (i=2;i<=n;i++)
        if (w[i] != w[i-1])
            w[++k] = w[i];
    for (i=1;i<=n;i++)
        v[i] = cautare_binara (w,k,v[i]);

    for (i=2;i<=n;i++){
        for (j=i-1;j;j--){
            if (v[i] == v[j]){
                d[i][v[j]]++;
                if (d[i][v[j]] >= MOD)
                    d[i][v[j]] -= MOD;
            }
            if (v[i] < v[j]){
                d[i][v[j]] += d[j][v[i]-1]+1;
                if (d[i][v[j]] >= MOD)
                    d[i][v[j]] -= MOD;
            }
            if (v[i] > v[j]){
                d[i][v[j]] += d[j][k]-d[j][v[i]]+1;
                if (d[i][v[j]] >= MOD)
                    d[i][v[j]] -= MOD;
            }}
        for (j=1;j<=k;j++){
            sol += d[i][j];
            if (sol >= MOD)
                sol -= MOD;
            d[i][j] += d[i][j-1];
            if (d[i][j] >= MOD)
                d[i][j] -=MOD;
        }}

    fout<<sol;

    return 0;
}