#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 2056
#define LL long long

LL mod = (LL)(1 << 16);

int N; LL sol;
int S[maxn];
LL dyn[maxn];
LL P[maxn][maxn];
struct Elem {
    int val, poz;
} A[maxn];

int cmp(Elem a, Elem b) {
    return a.val < b.val;
}

int main() {
    FILE *f1=fopen("psir.in", "r"), *f2=fopen("psir.out", "w");
    int i, j, p, q;

    fscanf(f1, "%d\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d", &A[i].val);
         A[i].poz = i;
    }

    mod = (LL)mod * mod;

    sort(A+1, A+N+1, cmp);

    p = 0;
    for(i=1; i<=N; i++) {
         if(A[i].val != A[i-1].val) {
              p ++;
         }

         S[ A[i].poz ] = p;
    }

    for(i=1; i<=N; i++) {
         memset(dyn, 0, sizeof(dyn));

         for(j=1; j<S[i]; j++) {
              dyn[j] = (dyn[j] + P[j][N] - P[j][ S[i] ]) % mod;
         }
         for(j=S[i]+1; j<=N; j++) {
              dyn[j] = (dyn[j] + P[j][ S[i] - 1 ]) % mod;
         }
         for(j=1; j<i; j++) {
              dyn[ S[j] ] = (dyn[ S[j] ] + 1) % mod;
         }

         for(j=1; j<=N; j++) {
              //update in AIB
              dyn[j] = (dyn[j] + dyn[j-1]) % mod;
              P[ S[i] ][j] = (P[ S[i] ][j] + dyn[j]) % mod;
         }
    }

    for(i=1; i<=N; i++) {
         sol = (sol + P[i][N]) % mod;
    }

    fprintf(f2, "%lld\n", sol);
    fclose(f1); fclose(f2);
    return 0;
}