#include <stdio.h>
#include <algorithm>

using namespace std;

const char iname[] = "psir.in";
const char oname[] = "psir.out";

#define MAX_N  2000

typedef unsigned int i32;

typedef long long i64;

const i64 modulo = 0xffffffff;

int n, P[MAX_N], m, Q[MAX_N], log;

int F[MAX_N];


void read_in(void)
{    
     FILE *fi = fopen(iname, "r");
     int i;
     
     fscanf(fi, "%d", &n);
     for (i = 0; i < n; ++ i)
         fscanf(fi, "%d", &P[i]), Q[i] = P[i];
     fclose(fi);
     
     sort(Q, Q + n);
     for (i = m = 0; i < n; ++ i) {
         if (i == 0)
             m ++;
         else if (i > 0) 
             if (Q[m - 1] != Q[i]) 
                 Q[m ++] = Q[i];
     }
     for (log = 1; log < m; log <<= 1) ;
}

i32 A[MAX_N][MAX_N];

int search(int Q[], int n, int val)
{
    int k;
    int stp = log;

    for (k = 0; stp; stp >>= 1) {
        if ((k + stp < n) && (Q[k + stp] <= val))
            k = k + stp;
    }
    return k;
}

i64 query(i32 A[], int lo, int hi)
{
    if (hi < lo)   return 0;
    
    i64 sum;
 
    if (lo > 0)   
        sum = ((i64)A[hi]) - ((i64)A[lo - 1]);
    else
        sum = ((i64)A[hi]);
    if (sum < 0)
        sum += modulo + 1;
    return sum;
}

i32 f(void)
{
    int i;
    int j;
    int k;
    int pi;
    i64 cnt;
    i64 rez = 0;
    i64 tmp;
    
    for (i = 0; i < n; ++ i)
        F[i] = search(Q, m, P[i]);
        
    for (i = 1; i < n; ++ i) {
        for (j = 0; j < i; ++ j) {
            k = F[i];
            if (P[j] < P[i])   // aduna elementele mai mari decat P[i]
                cnt = query(A[j], k + 1, m - 1);
            else if (P[j] > P[i])   // aduna elementele mai mici decat P[i]
                cnt = query(A[j], 0, k - 1);
            else
                cnt = 0;
            
            k = F[j], tmp = (((i64)A[i][k]) + (cnt + 1)) & modulo;
            A[i][k] = ((i32)tmp);     // update
            
            rez = (rez + (cnt + 1)) & modulo;
        }
        for (j = 1; j < m; ++ j) {
            tmp = (((i64)A[i][j]) + ((i64)A[i][j - 1])) & modulo;
            A[i][j] = ((i32)tmp);
        }
    }
    return ((i32)rez);
}

void print(const i32 ans)
{
     FILE *fo = fopen(oname, "w");
     fprintf(fo, "%u\n", ans);
     fclose(fo);
}

int main(void)
{
    read_in();
    print(f());
    return 0;
}