#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

#define in "psir.in"
#define out "psir.out"
#define dim 2001

long long modulo = 4294967296LL;

int N;
long long A[dim], P[dim];
vector< vector<long long> > B;

int main()
{
    freopen(in,"r",stdin);
    freopen(out,"w",stdout);
    
    scanf("%d", &N);
    B.resize(N+1);
    for ( int i = 1; i <= N; i++ )
    {
        B[i].resize(N+1);
        scanf("%lld", &P[i]);
    }
    
    for ( int i = 1; i <= N; i++ )
        for ( int j = i+1; j <= N; j++ )
            B[i][j] = 0;
    
    long long G;
    int poz;
    
    for ( int i = 1; i < N-1; i++ )
        for ( int j = i+1; j < N; j++ )
            for ( int k = j+1; k <= N; k++ )
            {
                if ( (P[k] < P[i] && P[k] > P[j]) || (P[k] < P[j] && P[k] > P[i]) ) 
                {
                     G = A[k] + B[i][j] + 1;
                     while ( G >= modulo ) G -= modulo;
                     A[k] = G;
                     
                     G = B[j][k] + 1;
                     while ( G >= modulo ) G -= modulo;
                     B[j][k] = G;
                }
                /*if ( P[k] < P[j] && P[k] > P[i] )
                {
                     G = A[k] + B[i][j] + 1;
                     while ( G >= modulo ) G -= modulo;
                     A[k] = G;
                     
                     G = (B[j][k] + 1);
                     while ( G >= modulo ) G -= modulo;
                     B[j][k] = G;
                }*/
            }       
             
    long long t = 0;
    for ( int i = 1; i <= N; i++ )
    {
        G = t + A[i];
        while ( G >= modulo ) G -= modulo;
        t = G;
    }
    
    G = t+N*(N-1)/2;
    while ( G >= modulo ) G -= modulo;
    t = G;
    
    printf("%lld", t);
}