#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define sz size()
#define pb push_back
#define x first
#define y second
#define mp make_pair

#define Nmax 2048

int n;
unsigned int rez;
int v[Nmax];

long long unu = 1, aux;

vector< pair<short int, unsigned int> > v1[Nmax], v2[Nmax];

void readdata()
{
    freopen("psir.in", "r", stdin);
    freopen("psir.out", "w", stdout);
    
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &v[i]);
}

inline int search1(int a, int val)
{
    int st = 0, dr = v1[a].sz-1, m;
    
    while (st < dr)
    {
        m = (st+dr+1)/2;
        if (v[v1[a][m].x] < val) st = m;
        else dr = m-1;
    }
    
    if (v1[a].sz == 0) return -1;
    
    if (v[v1[a][st].x] >= val) return -1;
    return st;
}

inline int search2(int a, int val)
{
    int st = 0, dr = v2[a].sz-1, m;
    while (st < dr)
    {
        m = (st+dr)/2;
        if (v[v2[a][m].x] > val) dr = m;
        else st = m+1;
    }
    
    if (v2[a].sz == 0) return -1;    
    
    if (v[v2[a][st].x] <= val) return -1;
    return st;
}

inline void aduna(unsigned int &a, unsigned int b)
{
    long long aux = a;
    aux += b;
    aux &= unu;
    
    a = aux;
}

inline int cmp(pair<short int, unsigned int> a, pair<short int, unsigned int> b)
{ return v[a.x] < v[b.x]; }

void solve()
{
    int i, j, k;
    unsigned int nr[Nmax];
    vector< pair<short int, unsigned int> > aux;
    
    unu <<= 32;
    unu -= 1;
    
    for (j = 2; j <= n; ++j)
    {
        for (i = 1; i < j; ++i)
        {
            nr[i] = 1;
            if (v[i] > v[j])
            {
                k = search1(i, v[j]);
                if (k != -1) aduna(nr[i], v1[i][k].y);
            }
            if (v[i] < v[j])
            {
                k = search2(i, v[j]);                
                if (k != -1) aduna(nr[i], v2[i][k].y);
            }
        }
        
        for (i = 1; i < j; ++i)
            aduna(rez, nr[i]);
        
        aux.clear();
        for (i = 1; i < j; ++i)
            if (v[i] < v[j])
                aux.pb(mp(i, nr[i]));
        sort(aux.begin(), aux.end(), cmp);
        for (i = 1; i < aux.sz; ++i)
            aduna(aux[i].y, aux[i-1].y);
        v1[j].reserve(aux.sz);
        for (i = 0; i < aux.sz; ++i)
            v1[j].pb( aux[i] );
            
        aux.clear();
        for (i = 1; i < j; ++i)
            if (v[i] > v[j])
                aux.pb(mp(i, nr[i]));
        sort(aux.begin(), aux.end(), cmp);
        for (i = aux.sz-2; i >= 0; --i)
            aduna(aux[i].y, aux[i+1].y);
        v2[j].reserve(aux.sz);
        for (i = 0; i < aux.sz; ++i)
            v2[j].pb(aux[i]);
    }
    
    unu = rez;
    printf("%lld\n", unu);
}

int main()
{
    readdata();
    solve();
    return 0;
}