#include <bits/stdc++.h>

#define ll long long
#define el cout << '\n'

using namespace std;

struct Segment_Tree
{
    struct Node
    {
        int l, r;
        ll sum, lazy, sum_mul;

        Node(int l = 0, int r = 0, ll sum = 0, ll lazy = 0, ll sum_mul = 0) :
            sum(sum), lazy(lazy), sum_mul(sum_mul) {};
        bool operator == (const Node &other) const
        {
            return sum == other.sum && lazy == other.lazy && sum_mul == other.sum_mul;
        }
    };

    int n;
    vector<Node> tree;
    Node nll;

    Segment_Tree(int n = 0) : n(n)
    {
        nll = Node(-1e9, -1e9, -1e18, -1e18, -1e18);
        tree.assign(4 * n + 10, Node(0, 0, 0, 0, 0));
    }
    void update_node(Node &a, int l, int r, ll val)
    {
        ll len = r - l + 1;
        a.l = l;
        a.r = r;
        a.sum += len * val;
        a.lazy += val;
        a.sum_mul += (len + 1) * len / 2 * val;
    }
    void push(int id, int l, int r)
    {
        if (tree[id].lazy == 0)
            return ;
        int m = l + r >> 1;
        update_node(tree[id << 1], l, m, tree[id].lazy);
        update_node(tree[id << 1 | 1], m + 1, r, tree[id].lazy);
        tree[id].lazy = 0;
    }
    Node merge_node(Node a, Node b, int l, int r)
    {
        if (a == nll)
            return b;
        if (b == nll)
            return a;
        Node ans;
        ans.sum = a.sum + b.sum;
        ans.lazy = 0;
        ans.sum_mul = a.sum_mul + (b.r - b.l + 1) * a.sum + b.sum_mul;
        ans.l = a.l;
        ans.r = b.r;
        return ans;
    }
    void update(int id, int l, int r, int u, int v, ll val)
    {
        if (r < u || l > v)
            return ;
        if (u <= l && r <= v)
        {
            update_node(tree[id], l, r, val);
            return ;
        }
        int m = l + r >> 1;
        push(id, l, r);
        update(id << 1, l, m, u, v, val);
        update(id << 1 | 1, m + 1, r, u, v, val);
        tree[id] = merge_node(tree[id << 1], tree[id << 1 | 1], l, r);
    }
    Node get(int id, int l, int r, int u, int v)
    {
        if (r < u || l > v)
            return nll;
        if (u <= l && r <= v)
        {
//            cout << l << ' ' << r << ' ' << tree[id].sum << ' ' << tree[id].sum_mul, el;
            return tree[id];
        }
        int m = l + r >> 1;
        push(id, l, r);
        Node a = get(id << 1, l, m, u, v);
        Node b = get(id << 1 | 1, m + 1, r, u, v);
         return merge_node(a, b, l, r);
    }
    void update(int l, int r, ll val)
    {
        if (r < l)
            return ;
        update(1, 1, n, l, r, val);
    }
    Node get(int l, int r)
    {
        if (r < l)
            return Node(0, 0, 0);
        return get(1, 1, n, l, r);
    }
};

const int maxn = 2e5;

int n, a[maxn + 10];
ll ans = 0;
vector<int> v, pos[maxn + 10];
Segment_Tree st;

int get_id(int x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen("VBAUCU.INP", "r"))
    {
        freopen("VBAUCU.INP", "r", stdin);
        freopen("VBAUCU.OUT", "w", stdout);
    }

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        v.push_back(a[i]);
    }
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    for (int i = 1; i <= n; i++)
    {
        a[i] = get_id(a[i]);
        if (pos[a[i]].size() == 0)
            pos[a[i]].push_back(1);
        pos[a[i]].push_back(i);
    }
    st = Segment_Tree(2 * n + 2);
    st.update(n + 1, n + 1, 1);

    for (int i = 1; i <= v.size(); i++)
    {
//        cout << i, el;
        pos[i].push_back(n + 1);
        for (int j = 1; j < pos[i].size(); j++)
        {
            int pre_l = -pos[i][j - 1] + 2 * (j - 1) + n + 1;
            int pre_r = -(pos[i][j] - 1) + 2 * (j - 1) + n + 1;
            int len = pos[i][j] - pos[i][j - 1];
            if (pos[i][j - 1] > pos[i][j] - 1)
                continue;
            int x = st.get(1, pre_r - 1).sum * len + st.get(pre_r, pre_l - 1).sum_mul;
            ans += x;
//            cout << pos[i][j - 1] << ' ' << pos[i][j] - 1 << ' ' << pre_l << ' ' << pre_r << ' ' << x, el;
            st.update(pre_r, pre_l, 1);
        }
//        cout << ans, el;
        for (int j = 1; j < pos[i].size(); j++)
        {
            ll pre_l = -pos[i][j - 1] + 2 * (j - 1) + n + 1;
            ll pre_r = -(pos[i][j] - 1) + 2 * (j - 1) + n + 1;

            if (pos[i][j - 1] > pos[i][j] - 1)
                continue;
            st.update(pre_r, pre_l, -1);
        }
    }
    cout << ans;
}