#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define maxn 2056
#define LL long long
#define LSB(x) (x&(x-1))^x

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

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

void update(int nr, int poz, int val) {
    while(poz <= N) {
         AIB[nr][poz] = (AIB[nr][poz] + val) % mod;
         poz += LSB(poz);
    }
}

int query(int nr, int poz) {
    int rez = 0;
    while(poz) {
         rez = (rez + AIB[nr][poz]) % mod;
         poz -= LSB(poz);
    }

    return rez;
}

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] + query(j, N) - query(j, S[i])) % mod;
         }
         for(j=S[i]+1; j<=N; j++) {
              dyn[j] = (dyn[j] + query(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
              update(S[i], j, dyn[j]);
         }
    }

    for(i=1; i<=N; i++) {
         for(j=1; j<=N; j++) {
              sol = (sol + query(i, j) - query(i, j-1)) % mod;
         }
    }

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