# include <fstream>
# include <algorithm>
# define DIM 2010
# define MOD ((1LL)<<32)
using namespace std;
ifstream fin("psir.in");
ofstream fout("psir.out");
unsigned int d[DIM][DIM],s[DIM][DIM],v[DIM],sor[DIM],n,k,i,j,sol;
long long aux;
int cauta(int val,int k){
    int step,j;
    for(step=1;step<=k;step*=2);
    for(j=0;step;step/=2)
        if(j+step<=k&&sor[j+step]<=val)
            j+=step;
    return j;
}
void verifica(long long &a){
    if(a>=MOD)
        a-=MOD;
    if(aux<0)
        aux+=MOD;
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>v[i];
        sor[i]=v[i];
    }
    sort(sor+1,sor+n+1);
    k++;
    for(i=2;i<=n;i++)
        if(sor[i]!=sor[k])
            sor[++k]=sor[i];
    for(i=1;i<=n;i++)
        v[i]=cauta(v[i],k);
    for(i=1;i<=n;i++){
        for(j=0;j<=k;j++){
            if(j==0){
                aux=d[v[i]][0];
                aux++;
                verifica(aux);
                d[v[i]][0]=aux;
                continue;
            }
            if(v[i]==j){
                aux=d[j][j];
                aux+=d[j][0]-1;
                verifica(aux);
                d[j][j]=aux;
                continue;
            }
            if(v[i]>j){
                aux=d[v[i]][j];
                aux+=s[j][k]-s[j][v[i]];
                aux+=d[j][0];
                verifica(aux);
                d[v[i]][j]=aux;
            }
            else{
                aux=d[v[i]][j];
                aux+=s[j][v[i]-1];
                aux+=d[j][0];
                verifica(aux);
                d[v[i]][j]=aux;
            }
        }
        for(j=1;j<=k;j++){
            if(v[i]==j){
                s[v[i]][j]=s[v[i]][j-1];
                continue;
            }
            aux=s[v[i]][j-1];
            aux+=d[v[i]][j];
            verifica(aux);
            s[v[i]][j]=aux;
        }
        aux=s[v[i]][k];
        aux+=d[v[i]][v[i]];
        verifica(aux);
        s[v[i]][k+1]=aux;
    }
    for(i=1;i<=k;i++){
        aux=sol;
        aux+=s[i][k+1];
        verifica(aux);
        sol=aux;
    }
    fout<<sol<<"\n";
    return 0;
}