#include <iostream>
#include <cstdio>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

const ll mod=(1LL<<32);
ll add(ll a,ll b)
{
        a+=b;
        if(a>=mod)
                return a-mod;
        if(a<0)
                return a+mod;
        return a;
}

const int N=2000+7;
int n,a[N];
map <int,int> t;
set <int> s;
ll dp[N][N];

int main()
{
        freopen("psir.in","r",stdin);
        freopen("psir.out","w",stdout);

        cin>>n;
        for(int i=1;i<=n;i++)
        {
                cin>>a[i];
                s.insert(a[i]);
        }

        int cur=0;
        for(auto &x : s)
                t[x]=++cur;

        for(int i=1;i<=n;i++)
                a[i]=t[a[i]];

        for(int i=1;i<=n;i++)
        {
                for(int j=1;j<i;j++)
                        dp[a[j]][a[i]]=add(dp[a[j]][a[i]],1);
                int x=a[i];

                for(int y=1;y<x;y++)
                        for(int z=x+1;z<=cur;z++)
                        {
                                for(int j=1;j<=2;j++)
                                {
                                        dp[z][x]=add(dp[z][x],dp[y][z]);
                                        swap(z,y);
                                }
                        }
        }

        ll sum=0;
        for(int i=1;i<=cur;i++)
                for(int j=1;j<=cur;j++)
                        sum=add(sum,dp[i][j]);
        cout<<sum<<"\n";

        return 0;
}