RT，思路为先找到满足对恰出现一次的的数为a[i]的[l,r]，然后考虑把这个区间拆成[l,i],[i,r]，把左边区间扔到线段树上(match)，线段树每个点维护一个set用来记录这个点能到哪些区间(link)，最后将线段树每个叶子到根的路径上的所有区间暴力并起来(find,link)，并对这些区间的长度求和。

目测link不对，但不知道错哪。

#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define D double
#define LD long double
#define LL long long
#define ULL unsigned long long
#define S string
#define fi first
#define se second
#define mp make_pair
using namespace std;

struct node
{
    int l;
    int r;
    set<pair<int, int>> s;
} t[200010 << 2];

int L[200010], R[200010];
int lst[200010];
int a[200010];

void build(int rt, int l, int r)
{
    t[rt].l = l, t[rt].r = r;
    if (l == r)
    {
        return;
    }
    int mid = (l + r) / 2;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    return;
}

int match_l, match_r; // i is a english men

void link(int rt, int l, int r)
{
    // cout << 1;
    t[rt].s.insert(mp(l, r));
    int nl = l, nr = r;
    for (auto i = t[rt].s.find(mp(l, r)); i != t[rt].s.begin(); i--)
    {
        auto it = i;
        it--;
        if (it->second >= i->first)
        {
            nl = it->first, nr = max(i->second, it->second);
            t[rt].s.erase(i);
            t[rt].s.erase(it);
            t[rt].s.insert(mp(nl, nr));
            i = t[rt].s.find(mp(nl, nr));
        }
        else
        {
            break;
        }
    }
    // cout << 2;
    std::set<std::pair<int, int>>::iterator i = t[rt].s.find(mp(nl, nr)), it;
    it = i;
    it++;
    for (; it != t[rt].s.end();)
    {
        if (i->second >= it->first)
        {
            nl = i->first, nr = max(i->second, it->second);
            t[rt].s.erase(i);
            t[rt].s.erase(it);
            t[rt].s.insert(mp(nl, nr));
            i = t[rt].s.find(mp(nl, nr));
            it = i;
            it++;
        }
        else
        {
            break;
        }
    }
    // cout << 2;
}

void match(int rt, int l, int r)
{
    if (l <= t[rt].l && t[rt].r <= r)
    {
        link(rt, match_l, match_r);
        return;
    }
    int mid = (t[rt].l + t[rt].r) / 2;
    if (l <= mid)
    {
        match(rt << 1, l, r);
    }
    if (r > mid)
    {
        match(rt << 1 | 1, l, r);
    }
    return;
}

void find(int rt, int x)
{
    for (auto i : t[rt].s)
    {
        link(0, i.fi, i.se);
    }
    if (t[rt].l == t[rt].r)
    {
        return;
    }
    int mid = (t[rt].l + t[rt].r) / 2;
    if (x <= mid)
    {
        find(rt << 1, x);
    }
    else
    {
        find(rt << 1 | 1, x);
    }
    return;
}

int main()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++)
    {
        lst[i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        L[i] = lst[a[i]] + 1;
        lst[a[i]] = i;
    }
    for (int i = 1; i <= n; i++)
    {
        lst[i] = n + 1;
    }
    for (int i = n; i >= 1; i--)
    {
        R[i] = lst[a[i]] - 1;
        lst[a[i]] = i;
    }
    // for (int i = 1; i <= n; i++)
    // {
    //     cout << L[i] << ' ' << R[i] << '\n';
    // }
    build(1, 1, n);
    for (int i = 1; i <= n; i++)
    {
        match_l = i, match_r = R[i];
        match(1, L[i], i);
    }
    LL ans = 0;
    for (int i = 1; i <= n; i++)
    {
        t[0].s.clear();
        find(1, i);
        for (auto i : t[0].s)
        {
            ans += i.se - i.fi + 1;
        }
    }
    // cout << '\n';
    cout << ans;
    return 0;
}