#include <bits/stdc++.h>
using namespace std;

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

struct group {
    int val;
    unsigned int cnt;

    bool operator < (const group& aux) const
    {
        return val < aux.val;
    }
};

vector <group> a[2001];
int n, v[2001];
const long long mod = pow(2, 32);

int main()
{
    fin >> n;

    int l, r, m, pos;
    long long x, y;
    long long res = 0;

    for (int i = 1; i <= n; i++)
    {
        fin >> v[i];

        for (int j = i - 1; j >= 1; j--)
        {
            if (v[j] < v[i])
            {
                l = 0, r = a[j].size() - 1, pos = -1;

                while (l <= r)
                {
                    m = (l + r) >> 1;

                    if (a[j][m].val > v[i])
                    {
                        pos = m;
                        r = m - 1;
                    }
                    else
                        l = m + 1;
                }

                if (pos == -1)
                    a[i].push_back({ v[j], 1 });
                else
                {
                    x = a[j].back().cnt + 1;
                    if (x >= mod)
                        x -= mod;
                    if (pos)
                        x -= a[j][pos - 1].cnt;
                    if (x < 0)
                        x += mod;
                    a[i].push_back({ v[j], (unsigned int)x });
                }
            }
            else
            {
                l = 0, r = a[j].size() - 1, pos = -1;

                while (l <= r)
                {
                    m = (l + r) >> 1;

                    if (a[j][m].val < v[i])
                    {
                        pos = m;
                        l = m + 1;
                    }
                    else
                        r = m - 1;
                }

                if (pos == -1)
                    a[i].push_back({ v[j], 1 });
                else
                {
                    x = a[j][pos].cnt + 1;
                    if (x >= mod)
                        x -= mod;
                    a[i].push_back({ v[j], (unsigned int)x });
                }
            }
        }

        sort(a[i].begin(), a[i].end());

        int j = 0, k = 0;

        while (j < a[i].size())
        {
            a[i][k] = a[i][j++];
            x = a[i][k].cnt;

            while (j < a[i].size() && a[i][j].val == a[i][k].val)
            {
                x += a[i][j].cnt;
                if (x >= mod)
                    x -= mod;
                j++;
            }

            a[i][k].cnt = x;
            k++;
        }

        while (a[i].size() > k)
            a[i].pop_back();

        long long last = 0;

        for (int j = 0; j < a[i].size(); j++)
        {
            last += a[i][j].cnt;
            if (last >= mod)
                last -= mod;
            a[i][j].cnt = last;
        }

        if (a[i].size())
        {
            res += a[i][a[i].size() - 1].cnt;
            if (res >= mod)
                res -= mod;
        }
    }

    fout << res;
    
    return 0;
}