#include <fstream>
#include <map>
#include <algorithm>

using namespace std;

const int NMAX = 2005;
const long long MOD = (1LL << 32);
ifstream cin ("psir.in");
ofstream cout ("psir.out");

int init[NMAX], cop[NMAX], v[NMAX];
long long dp[NMAX], f[NMAX];
int main()
{
    int n;
    cin>>n;
    map <int, int> my_map;
    for(int i = 1; i <= n; ++i) {
        cin>>v[i];
        cop[i] = v[i];
    }
    sort(cop +  1, cop + n + 1);
    int cont = 1;
    cop[0] = 0;
    for(int i = 1; i <= n; ++i)
        if(cop[i] > cop[i - 1]) {
            my_map[cop[i]] = cont;
            cont++;
        }
    for(int i = 1; i <= n; ++i)
        v[i] = my_map[v[i]];
    for(int i = 1; i <= n; ++i)
        f[v[i]]++;
    for(int i = 1; i <= n; ++i)
        dp[i] = 1;
    for(int i3 = 2; i3 <= n; ++i3) {
        for(int i2 = 1; i2 < i3; ++i2) {
            for(int i1 = 1; i1 < i2; ++i1)
                if((v[i1] < v[i3] && v[i3] < v[i2]) || (v[i1] > v[i3] && v[i3] > v[i2]))
                    dp[i3] = (dp[i3] + dp[i2]) % MOD;
        }
    }
    long long sum = 0;
   // for(int i = 1; i <= NMAX; ++i)
   //     cnt = cnt + ((f[i] * (f[i] - 1)) >> 1);
   // cout<<(MOD + dp[n] + 1LL * cont * (cont - 1) / 2 - cnt) % MOD<<"\n";
    for(int i = 1; i <= n; ++i)
        sum = (sum + dp[i]) % MOD;
    cout<<(MOD + sum + n * (n - 1) / 2 - n) % MOD<<"\n";
    return 0;
}