#include <stdio.h>
#include <string.h>

#define MAXN 2048
#define MOD (long long)(1<<30)*(1<<2)

typedef long long llong;

int N, P[MAXN];
llong A[MAXN][2], res;

void solve(void)
{
    int i, j;

    for(i = 2; i <= N; i++)
    {
        // pentru 0, a[i] > a[i-1]
        for(j = 1; j < i; j++)
         if(P[i] > P[j])
         {
            A[i][0]++;
            if(A[i][0] >= MOD)
                A[i][0] -= MOD;
            A[i][0] += A[j][1];
            if(A[i][0] >= MOD)
                A[i][0] -= MOD;
         }
        // pentru 1, a[i] < a[i-1]
        for(j = 1; j < i; j++)
         if(P[i] < P[j])
         {
            A[i][1]++;
            if(A[i][1] >= MOD)
                A[i][1] -= MOD;
            A[i][1] += A[j][0];
            if(A[i][1] >= MOD)
                A[i][1] -= MOD;
         }
        // daca sunt egale
        for(j = 1; j < i; j++)
         if(P[i] == P[j])
            res++, res = (res >= MOD ? res-MOD : res);

        res += A[i][0];
        if(res >= MOD)
            res -= MOD;
        res += A[i][1];
        if(res >= MOD)
            res -= MOD;
    }
}

void read_data(void)
{
    int i;

    scanf("%d ", &N);

    for(i = 1; i <= N; i++)
        scanf("%d ", &P[i]);
}

void write_data(void)
{
    printf("%lld\n", res);
}

int main(void)
{
    freopen("psir.in", "rt", stdin);
    freopen("psir.out", "wt", stdout);

    read_data();
    solve();
    write_data();

    return 0;
}