#include <bits/stdc++.h>
#define MOD (1LL<<32)
#define Nmax 2005

using namespace std;

unsigned int n,a[Nmax],v[Nmax],l,dp[Nmax][Nmax],sum[Nmax][Nmax];
unordered_map <int,int> M;

inline void Normalize()
{
    sort(v+1,v+l+1);
    M[v[1]]=1;
    for(int i=2;i<=l;++i) M[v[i]]=M[v[i-1]]+(v[i]>v[i-1]);
}

int main()
{
    unsigned int i,j,sol=0;
    ifstream cin("psir.in");
    ofstream cout("psir.out");
    cin>>n;
    for(i=1;i<=n;++i)
    {
        cin>>a[i]; v[++l]=a[i];
    }

    Normalize();
    for(i=1;i<=n;++i) a[i]=M[a[i]];

    for(i=1;i<=n;++i)
        for(j=i-1;j;--j) dp[i][j]=1;

    for(i=1;i<=n;++i)
    {
        for(j=i-1;j;--j)
        {
            if(a[i]!=a[j])
            {
                if(a[i]<a[j]) dp[i][j]=(sum[j][a[i]-1]+dp[i][j])%MOD;
                else dp[i][j]=(1LL*sum[j][n]-sum[j][a[i]]+MOD+dp[i][j])%MOD;
            }
            sol=(sol+dp[i][j])%MOD;
            sum[i][a[j]]=(sum[i][a[j]]+dp[i][j])%MOD;
        }
        for(j=1;j<=n;++j) sum[i][j]=(sum[i][j-1]+sum[i][j])%MOD;
    }

    cout<<sol<<"\n";
    return 0;
}