#include <bits/stdc++.h>
#define ll long long
#define ld long double

using namespace std;

const ll mod = (1ll << 32);
const ll INF = 1e16;  

ifstream fin ("psir.in");
ofstream fout ("psir.out");

int n, v[2002], a[2002];
ll dp[2002][2002], ans;
ll aib[2002][2002];

int query (int lol, int x) {
  int s = 0;
  for (int i = x; i; i -= (i & -i))
    s += aib[lol][x];
  return s;
}

void add (ll &a, ll b);

void update (int lol, int x, ll val) {
  for (int i = x; i <= n; i += (i & -i))
     add(aib[lol][i], val);
}

void add (ll &a, ll b) {
  a += b;
  if (a < 0)
    a -= mod;
  if (a >= mod)
    a -= mod;
}

int main()   
{
  fin >> n;
  for (int i = 1; i <= n; i++) {
    fin >> v[i];
    a[i] = v[i];
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++)
    v[i] = lower_bound(a + 1, a + n + 1, v[i]) - a;
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
      if (v[i] == v[j]) {
        add(ans, 1);
        continue;
      }
      if (v[i] > v[j]) {
        add(dp[i][j], query(i, v[j] - 1));
      }
      else 
        add(dp[i][j], query(i, n) - query(i, v[j]));
      add(dp[i][j], 1);
      update(j, v[i], dp[i][j]);
      add(ans, dp[i][j]);
    }
  fout << ans << "\n";
  return 0;
}