#ifndef LOCAL
    #pragma GCC optimize("O3")
    #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const int MOD = (1LL << 32);
const int NMAX = 2e3 + 5;
/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("psir.in");
    ofstream out("psir.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

int N;
int sol;
int v[NMAX];
int dp[NMAX][NMAX];

struct AIB_MIC
{
    int n;
    vector <int> data;

    AIB_MIC(){}

    AIB_MIC(int _n)
    {
        n = _n;
        data.resize(n + 1);
    }

    inline void update(int pos, int val)
    {
        while (pos <= n)
        {
            data[pos] += val;
            if (data[pos] >= MOD) data[pos] -= MOD;
            pos += (pos & (-pos));
        }
    }

    inline int query(int pos)
    {
        int suma = 0;
        while (pos)
        {
            suma += data[pos];
            if (suma >= MOD) suma -= MOD;
            pos -= (pos & (-pos));
        }

        return suma;
    }
} aib_mic[NMAX];

struct AIB_MARE
{
    int n;
    vector <int> data;

    AIB_MARE(){}

    AIB_MARE(int _n)
    {
        n = _n;
        data.resize(n + 1);
    }

    inline void update(int pos, int val)
    {
        while (pos)
        {
            data[pos] += val;
            if (data[pos] >= MOD) data[pos] -= MOD;
            pos -= (pos & (-pos));
        }
    }

    inline int query(int pos)
    {
        int suma = 0;
        while (pos <= n)
        {
            suma += data[pos];
            if (suma >= MOD) suma -= MOD;
            pos += (pos & (-pos));
        }

        return suma;
    }
} aib_mare[NMAX];
vector <int> valori;
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> N;

    for (int i = 1 ; i <= N ; ++ i)
    {
        cin >> v[i];
        valori.push_back(v[i]);
    }
}
///-------------------------------------
inline int get_norm(int x)
{
    return lower_bound(valori.begin(), valori.end(), x) - valori.begin() + 1;
}
///-------------------------------------
inline void Solution()
{
    sort(valori.begin(), valori.end());
    valori.erase(unique(valori.begin(), valori.end()), valori.end());

    for (int i = 1 ; i <= N ; ++ i)
    {
        aib_mic[i] = AIB_MIC(valori.size());
        aib_mare[i] = AIB_MARE(valori.size());
    }

    for (int i = 1 ; i <= N ; ++ i)
    {
        for (int j = i + 1 ; j <= N ; ++ j)
        {
            dp[i][j] = 1;
            if (v[i] > v[j])
                dp[i][j] += aib_mic[i].query(get_norm(v[j]) - 1);
            else
                dp[i][j] += aib_mare[i].query(get_norm(v[j]) + 1);

            if (dp[i][j] >= MOD) dp[i][j] -= MOD;
            
            sol += dp[i][j];
            if (sol >= MOD) sol -= MOD;

            aib_mic[j].update(get_norm(v[i]), dp[i][j]);
            aib_mare[j].update(get_norm(v[i]), dp[i][j]);
        }
    }
}
///-------------------------------------
inline void Output()
{
    cout << sol;
}
///-------------------------------------
signed main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}