# include <fstream>
# include <algorithm>
# define DIM 2010
# define MOD ((1LL)<<32)
using namespace std;
ifstream fin("psir.in");
ofstream fout("psir.out");
long long d[DIM][DIM],s[DIM][DIM],v[DIM],sor[DIM],n,k,i,j,sol;
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;
}
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){
                d[v[i]][0]++;
                verifica(d[v[i]][0]);
                continue;
            }
            if(v[i]==j){
                d[j][j]+=d[j][0]-1;
                verifica(d[j][j]);
                continue;
            }
            if(v[i]>j){
                d[v[i]][j]+=s[j][k]-s[j][v[i]]+d[j][0];
                verifica(d[v[i]][j]);
            }
            else{
                d[v[i]][j]+=s[j][v[i]-1]+d[j][0];
                verifica(d[v[i]][j]);
            }
        }
        for(j=1;j<=k;j++){
            if(v[i]==j){
                s[v[i]][j]=s[v[i]][j-1];
                continue;
            }
            s[v[i]][j]=s[v[i]][j-1]+d[v[i]][j];
            verifica(s[v[i]][j]);
        }
        s[v[i]][k+1]=s[v[i]][k]+d[v[i]][v[i]];
    }
    for(i=1;i<=k;i++){
        sol+=s[i][k+1];
        verifica(sol);
    }
    fout<<sol<<"\n";
    return 0;
}