#include <bits/stdc++.h>

using namespace std;
    
typedef long long ll;
const int  N = 1e6 + 12, MOD = 998244353;

int n, a[N], lst[N], prv[N];
ll t[N * 4], k[N * 4], add[N * 4];
void merge(int v) {
    t[v] = t[v + v] + t[v + v + 1];
    k[v] = k[v + v] + k[v + v + 1];
}

void inc(int v,int val) {
    t[v] += val * 1ll * k[v];
    add[v] += val;
}
void push(int v) {
    if(add[v]) {
        inc(v + v, add[v]);
        inc(v + v + 1, add[v]);
        add[v] = 0;
    }
}
void upd1(int pos,int val,int v = 1,int tl = 1,int tr = n) {
    if(tl == tr) {
        k[v] = val;
        t[v] = k[v] * t[v];
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        if(pos <= tm) upd1(pos,val,v+v,tl,tm);
        else upd1(pos,val,v+v+1,tm+1,tr);
        merge(v);
    }
}
void upd(int l,int r,int val,int v = 1,int tl = 1,int tr = n) {
    if(l > r || tl > r || l > tr) return;
    if(tl >= l && tr <= r) {
        inc(v,val); 
    } else {
        push(v);
        int tm = (tl + tr) >> 1;
        upd(l, r, val, v + v, tl, tm);
        upd(l, r, val, v + v + 1, tm + 1, tr);
        merge(v);
    }
}
ll get(int l,int r,int v = 1,int tl = 1,int tr = n) {
    if(l > r || tl > r || l > tr) return 0;
    if(tl >= l && tr <= r) {
        return t[v];
    } 
    push(v);
    int tm = (tl + tr) >> 1;
    return get(l, r, v + v, tl, tm) + get(l, r, v + v + 1, tm + 1, tr);
}
void test() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        prv[i] = lst[a[i]];
        lst[a[i]] = i;
    }
    ll res = 0;
    for(int i = 1; i <= n; i++) {
        int j = prv[i];
        if(j) {
            upd(prv[j] + 1,j - 1,-1);
            upd1(j,0);
        }
        res += get(j + 1,i - 1);
        upd1(i,1);
        upd(j + 1,i - 1,1);
    }
    cout << res << '\n';
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); 

    int t = 1; 
    // cin >> t;
    while(t--) 
        test();

    return 0;
}