#include <bits/stdc++.h>
#define ull unsigned long long int

using namespace std;

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

const long long int MOD = (1ll<<32);

struct elem
{
    int val, id;
};

struct cmp
{
    bool operator()(const elem& x, const elem& y) const
    {
        if (x.val != y.val)
            return x.val < y.val;
        return x.id < y.id;
    }
};

int sir[2009], normalizare[2009];
map<pair<int, int>, ull> currAns;
map<int, int> freq;
set<elem, cmp> st;
multiset<int> dr;

int main()
{
    ull ans = 0;
    int n;
    int nn = 0;
    fin >> n;
    for (int i = 1; i <= n; i++)
    {
        fin >> sir[i];
        if (!freq.count(sir[i]))
        {
            nn++;
            normalizare[nn] = sir[i];
        }
        dr.insert(sir[i]);
        freq[sir[i]]++;
    }

    sort(normalizare + 1, normalizare + nn + 1);

    dr.extract(sir[1]);
    st.insert({sir[1], 1});

    for (int i = 2; i <= n; i++)
    {
        dr.extract(sir[i]);
        ull ansj[2009];
        memset(ansj, 0, sizeof(ansj));

        int poz = lower_bound(normalizare + 1, normalizare + nn + 1, sir[i]) - normalizare;

        int goodDr = 0;
        for (int j = poz; j >= 1; j--)
        {
            int curr = normalizare[j];
            int nrSt = 0;

            auto start = st.lower_bound({curr, 0});
            auto end = st.upper_bound({curr, int(1e9)});

            ull otherSt = 0;
            for (auto it = start; it != end; it++)
            {
                nrSt++;
                otherSt = (otherSt + currAns[{it -> id, sir[i]}]) % MOD;
            }

            int nrDr = dr.count(curr);

            ans += (1ll * nrSt % MOD + otherSt % MOD) * (goodDr % MOD) % MOD;

            ansj[j + 1] = nrSt + otherSt;
            goodDr += nrDr;
        }

        ansj[poz] = 0;
        for (int j = poz - 1; j >= 1; j--)
        {
            ansj[j] = (ansj[j] % MOD + ansj[j + 1] % MOD) % MOD;
            currAns[{i, normalizare[j]}] = (currAns[{i, normalizare[j]}] + ansj[j]) % MOD;
        }

        st.insert({sir[i], i});











        memset(ansj, 0, sizeof(ansj));

        poz = upper_bound(normalizare + 1, normalizare + nn + 1, sir[i]) - normalizare;

        goodDr = 0;
        for (int j = poz; j <= nn; j++)
        {
            int curr = normalizare[j];
            int nrSt = 0;

            auto start = st.lower_bound({curr, 0});
            auto end = st.upper_bound({curr, int(1e9)});

            ull otherSt = 0;
            for (auto it = start; it != end; it++)
            {
                nrSt++;
                otherSt = (otherSt + currAns[{it -> id, sir[i]}]) % MOD;
            }

            int nrDr = dr.count(curr);

            ans += (1ll * nrSt % MOD + otherSt % MOD) * (goodDr % MOD) % MOD;

            ansj[j - 1] = nrSt + otherSt;
            goodDr += nrDr;
        }

        ansj[poz] = 0;
        for (int j = poz + 1; j <= nn; j++)
        {
            ansj[j] = (ansj[j] % MOD + ansj[j + 1] % MOD) % MOD;
            currAns[{i, normalizare[j]}] = (currAns[{i, normalizare[j]}] + ansj[j]) % MOD;
        }

        st.insert({sir[i], i});
    }
    fout << (1ull * ans % MOD + ((1ull * n * (n - 1)) / 2) % MOD) % MOD;
    return 0;
}