#pragma GCC optimize("03")
#define _CRT_SECURE_NO_WARNINGS
#include "bits/stdc++.h"
using namespace std;
using namespace chrono;
#define all(a) a.begin(), a.end()
#define allr(a) a.rbegin(), a.rend()
#define endl "\n"
#define fast_io ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
typedef int ll;
typedef long double ld;
struct Tree {
    vector<ll> tree,mod;
    map<ll, ll> posit;
    void init(ll n) {
        tree.resize(4*n,0);
        mod.resize(4 * n,-1);
    }
    void push(ll v) {
        if (mod[v] == -1)return;
         tree[v] = 0;
        if (v * 2 + 1 > (ll)tree.size()) {
            mod[v] = -1;
            return;
        }
        mod[v * 2] = mod[v];
        mod[v * 2 + 1] = mod[v];
        mod[v] = -1;
    }
    void update(ll v, ll tl, ll tr, ll pos) {
        if (tl == tr) {
            posit[tl] = v;
            tree[v]++;
            return;
        }
        ll mid = (tl + tr) / 2;
        if (pos <= mid) {
            update(v * 2, tl, mid, pos);
        }
        else {
            update(v * 2 + 1, mid + 1, tr, pos);
        }
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
    ll get_sum(ll v, ll tl, ll tr, ll l, ll r) {
        push(v);
        if (tl > r || tr < l) {
            return 0;
        }
        if (tl >= l && tr <= r) {
            return tree[v];
        }
        ll mid = (tl + tr) / 2;
        return get_sum(v * 2, tl, mid, l, r) + get_sum(v * 2 + 1, mid + 1, tr, l, r);
    }
    void update_sum(ll v, ll tl, ll tr, ll l, ll r) {
        push(v);
        if (tl > r || tr < l) {
            return;
        }
        if (tl >= l && tr <= r) {
            mod[v]=0;
            push(v);
            return;
        }
        ll mid = (tl + tr) / 2;
        update_sum(v * 2, tl, mid, l, r);
        update_sum(v * 2 + 1, mid + 1, tr, l, r);
        tree[v] = tree[v * 2] + tree[v * 2 + 1];
    }
    bool get(ll v, ll tl, ll tr, ll pos) {
        push(v);
        if (tl == tr) {
            return tree[v]>0;
        }
        ll mid = (tl + tr) / 2;
        if (pos <= mid) {
            get(v * 2, tl, mid, pos);
        }
        else {
            get(v * 2 + 1, mid + 1, tr, pos);
        }
    }
};
signed main() {
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    srand(time(NULL));
    ll t = 1;
    //cin >> t;
    while (t--) {
        ll n;
        cin >> n;
        vector<ll> a(n);
        struct My {
            ll inf = 1e9;
            ll mn=inf, mx=-1;
        };
        map<ll, ll>cur,pos;
        vector<My> cnt(n+1);
        for (ll i = 0; i < n; i++) {
            cin >> a[i];
            cnt[a[i]].mn = min(cnt[a[i]].mn, i);
            cnt[a[i]].mx = max(cnt[a[i]].mx, i);
            cur[a[i]]++,pos[a[i]]=i;
        }
        Tree seg,seg2;
        seg.init(n);
        seg2.init(n);
        for (ll i = 0; i < n; i++) {
            if (cur[a[i]] == 1 || i != cnt[a[i]].mn && i != cnt[a[i]].mx) {
                seg.update(1, 0, n - 1, i);
            }
            else {
                seg2.update(1, 0, n - 1, i);
            }
        }
        ll ans = 0;
        struct Cur {
            ll l, r;
        };
        vector<Cur>d;
        for (auto& i : cur) {

            if (i.second == 1) {
            }
            else {
                d.push_back({ cnt[i.first].mn, cnt[i.first].mx });
                ans += seg.get_sum(1, 0, n - 1, cnt[i.first].mn+1, cnt[i.first].mx-1);
                seg.update_sum(1, 0, n - 1, cnt[i.first].mn+1, cnt[i.first].mx-1);
            }
        }
        auto cmp = [&](Cur l, Cur r) {
            return l.l < r.l;
        };
        sort(all(d), cmp);
        for (Cur i : d) {
            if (seg2.get(1, 0, n - 1, i.l))
               if( seg2.get(1, 0, n - 1, i.r)) {
                ans += seg2.get_sum(1, 0, n - 1, i.l+1, i.r-1);
                seg2.update_sum(1, 0, n - 1, i.l+1, i.r-1);
            }
        }
        cout << ans << endl;
    }
}