#include<fstream>
#include<iostream>
#include<cstring>
#include<algorithm>
#define DN 2005
#define x first
#define y second
using namespace std;
ifstream fin("psir.in");
ofstream fout("psir.out");
unsigned int n,a[DN],dp[DN][DN],s[DN][DN],r[DN],p,st,dr,rez,viz[DN];
long long M=(1LL<<32);
pair<unsigned int,int>b[DN];
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
    {
        fin>>a[i];
        b[i]={a[i],i};
    }
    sort(b+1,b+n+1);
    for(int i=1;i<=n;i++)
        r[b[i].y]=i;
    for(int i=1;i<=n;i++)
    {
        p=r[i];
        st=0;
        dr=n+1;
        for(int j=p-1;j>0;j--)
            if(b[j].x<a[i])
            {
                st=j;
                break;
            }
        for(int j=p+1;j<=n;j++)
            if(b[j].x>a[i])
            {
                dr=j;
                break;
            }
        for(int j=1;j<p;j++)
            if(viz[j])
            {
                dp[p][j]=1;
                if(a[i]>b[j].x&&dr<=n)
                    dp[p][j]=(dp[p][j]+s[j][n]-s[j][dr-1]);
            }
        for(int j=p+1;j<=n;j++)
            if(viz[j])
            {
                dp[p][j]=1;
                if(a[i]<b[j].x&&st>0)
                    dp[p][j]=(dp[p][j]+s[j][st])%M;
            }
        for(int j=1;j<=n;j++)
            s[p][j]=(s[p][j-1]+dp[p][j])%M;
        rez=(rez+s[p][n])%M;
        viz[p]=1;
    }
    fout<<rez;
}