#include <algorithm>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <iostream>
#define nmax 2005
using namespace std;
ifstream f("psir.in");
ofstream g("psir.out");
unsigned int   v[nmax],n,cv[nmax],s[nmax][nmax];
unsigned int  mod=(1LL<<32);
int cb(int val)
{
    int st=1,dr=n,mij,rasp;
    while(st<=dr)
    {
        int mij=(st+dr)/2;
        if(cv[mij]<val)
        {
            st=mij+1;
        }
        else
        {
            if(cv[mij]==val)
            {
                rasp=mij;

            }
            dr=mij-1;
        }
    }
    return rasp;
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
    {
        f>>v[i];
        cv[i]=v[i];
    }
    sort(cv+1,cv+n+1);
    for(int i=1;i<=n;i++)
    {
        v[i]=cb(v[i]);

    }
  long long ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<i;j++)
        {long long sol=1;
            if(v[i]<v[j])
            {
                sol+=s[j][v[i]-1];
            }
            else if(v[i]>v[j])
            {
                sol+=s[j][n]-s[j][v[i]];

            }
             if(sol<0) sol+=mod;
            s[i][v[j]]=(s[i][v[j]]+sol)%mod;



        }
        for(int j=1;j<=n;j++)
        {
            s[i][j]=(s[i][j]+s[i][j-1])%mod;
        }
        ans=(ans+s[i][n])%mod;

    }
    g<<ans;
}