#include <fstream>
#include <algorithm>
#define MAXN 2005
#define NRM 4294967296
using namespace std;
ifstream f("psir.in");
ofstream g("psir.out");

unsigned int n,v[MAXN],ord[MAXN],nrmx,x,aib[MAXN][MAXN],cnt[MAXN];
long long y,S,sol;

bool Comp(int a,int b){
    return v[a]<v[b];}

void update(int a,int b);
unsigned int query(int a,int b);

int main()
{
    int i,j;
    f>>n;
    for(i=1;i<=n;i++){
        f>>v[i];
        ord[i]=i;}
    sort(ord+1,ord+n+1,Comp);
    for(i=1;i<=n;i++){
        x=v[ord[i]];
        nrmx++;
        for(i;i<=n&&v[ord[i]]==x;i++)
            v[ord[i]]=nrmx;
        i--;}
    cnt[v[1]]++;
    for(i=2;i<=n;i++){
        x=v[i];
        for(j=1;j<x;j++){
            y=1LL*query(j,nrmx)-query(j,x)+cnt[j];
            update(x,j);}
        y=cnt[x];
        update(x,x);
        for(j=x+1;j<=nrmx;j++){
            y=1LL*query(j,x-1)+cnt[j];
            update(x,j);}
        cnt[x]++;}
    for(i=1;i<=nrmx;i++)
        sol+=query(i,nrmx);
    g<<sol%NRM<<'\n';
    f.close();
    g.close();
    return 0;
}

void update(int a,int b){
    while(b<=nrmx){
        S=y+aib[a][b];
        if(S<0)
            S+=NRM;
        if(S>=NRM)
            S-=NRM;
        aib[a][b]=S;
        b+=(b&(-b));}}

unsigned int query(int a,int b){
    S=0;
    while(b){
        S+=aib[a][b];
        b-=(b&(-b));}
    return S%NRM;}