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

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;
set <int> st;
map <int,int> trans;
int n,a[N];
ll dp[N][N];
ll cop[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];
                st.insert(a[i]);
        }

        int bg=0;
        for(auto &x : st)
                trans[x]=++bg;

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

        for(int i=1;i<=n;i++)
        {
                for(int j=1;j<i;j++)
                {
                        int x=min(a[i],a[j]),y=max(a[i],a[j]);
                        cop[x][y]=add(cop[x][y],1);
                }

                int x=a[i];

                for(int st=x-1;st>=1;st--)
                        for(int dr=x+1;dr<=bg;dr++)
                        {
                                cop[st][x]=add(cop[st][x],dp[st][dr]);
                         //       cop[x][dr]=add(cop[x][dr],dp[st][dr]);
                        }

                for(int y=1;y<=bg;y++)
                {
                        dp[x][y]=cop[x][y];
                        dp[y][x]=cop[y][x];
                }

                continue;
                cout<<"# "<<i<<"\n";
                for(int x=1;x<=bg;x++)
                        for(int y=x;y<=bg;y++)
                                if(dp[x][y])
                                        cout<<x<<" "<<y<<" -> "<<dp[x][y]<<"\n";
                cout<<"\n\n";
        }

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

        return 0;
}