#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],dp[N][N],ndp[N][N];
map <int,int> t;

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

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

        int cur=0;
        for(auto &x : s)
        {
                cur++;
                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++)
                {
                        int mn=min(a[i],a[j]),mx=max(a[i],a[j]);
                        ndp[mn][mx]=add(ndp[mn][mx],1);
                }

                int x=a[i];

                for(int st=x-1;st>=1;st--)
                        for(int dr=x+1;dr<=cur;dr++)
                                ndp[st][x]=add(ndp[st][x],dp[st][dr]);

                for(int y=1;y<=cur;y++)
                {
                        dp[x][y]=add(ndp[x][y],dp[x][y]);
                        if(x!=y)
                                dp[y][x]=add(ndp[y][x],dp[y][x]);
                        ndp[x][y]=ndp[y][x]=0;
                }


        }

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