#include<fstream>
#include<algorithm>
#define MOD (1LL<<32)
using namespace std;
ifstream fin("psir.in");
ofstream fout("psir.out");
long long D[2005][2005], sol;
int v[2005], k, n;
pair<int,int> aux[2005];
inline long long F( long long x ){
    return ( x < MOD ) ? x : ( x - MOD );
}
int main(){
    fin >> n;
    for( int i = 1; i <= n; i++ ){
        fin >> aux[i].first;
        aux[i].second = i;
    }
    sort( aux + 1, aux + n + 1 );
    k = 0;
    for( int i = 1; i <= n; i++ ){
        if( aux[k].first != aux[i].first ){
            k++;
            aux[k] = aux[i];
        }
        v[ aux[i].second ] = k;
    }
    for( int i = 1; i <= n; i++ )
        for( int j = 1; j < i; j++ )
            D[i][ v[j] ] = 1;
    for( int i = 1; i <= n; i++ ){
        for( int j = 1; j < i; j++ ){
            if( v[j] < v[i] )
                D[i][ v[j] ] += D[j][ v[i] - 1 ];
            else
                D[i][ v[j] ] += D[j][ v[i] + 1 ];
            F( D[i][ v[j] ] );
        }
        for( int j = 1; j <= k; j++ ){
            D[i][j] += D[i][j - 1];
            F( D[i][j] );
        }
    }
    sol = 0;
    for( int j = 1; j <= n; j++ ){
        sol += D[j][k];
        F( sol );
    }
    fout << sol << "\n";
    return 0;
}