abc346G

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll nmax = 1e9+7;
const ll nmax2 = 998244353;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace __gnu_pbds;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<std::pair<ll, ll>, null_type, less<std::pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set_pair;

struct segment_tree {
    ll n;
    struct node {
        ll sum;
        ll maximum;
        ll minimum;
        bool lazytag;
    };

    std::vector<node> tree;

    node combine(node n1, node n2){
        node n3;
        n3.sum = n1.sum + n2.sum;
        n3.maximum = std::max(n1.maximum, n2.maximum);
        n3.minimum = std::min(n1.minimum, n2.minimum);
        n3.lazytag = false;
        return n3;
    }

    segment_tree (const std::vector<ll> &a){
        n = a.size();
        tree.resize(4 * n + 5);
        build_segment_tree(a, 1, 1, n);
    }

    void build_segment_tree(const std::vector<ll> &a, ll v, ll l, ll r){
        if (l == r){
            tree[v].sum = 0;
            tree[v].maximum = 0;
            tree[v].minimum = 0;
            return;
        }
        ll mid = (l + r) >> 1;
        build_segment_tree(a, 2 * v, l, mid);
        build_segment_tree(a, 2 * v + 1, mid + 1, r);
        tree[v] = combine(tree[2 * v], tree[2 * v + 1]);
    }

    void propogate(ll v, ll l, ll mid, ll r){
        if (tree[v].lazytag){
            tree[v].lazytag = false;
            tree[2 * v].lazytag = true;
            tree[2 * v + 1].lazytag = true;

            ll extra = (tree[v].sum - (tree[2 * v].sum + tree[2 * v + 1].sum)) / (r - l + 1);
            tree[2 * v].sum += extra * (mid - l + 1);
            tree[2 * v + 1].sum += extra * (r - mid);

            tree[2 * v].minimum = tree[v].minimum;
            tree[2 * v + 1].minimum = tree[v].minimum;

            tree[2 * v].maximum = tree[v].maximum;
            tree[2 * v + 1].maximum = tree[v].maximum;
        }
    }

    void range_update(ll v, ll l, ll r, ll tl, ll tr, ll val){
        if (l > r or r < tl or tr > l) return;
        if (tl <= l and r <= tr){
            tree[v].lazytag = true;
            tree[v].maximum += val;
            tree[v].minimum += val;
            tree[v].sum += (r - l + 1) * val;
            return;
        }
        ll mid = (l + r) >> 1;
        propogate(v, l, mid, r);
        range_update(2 * v, l, mid, tl, tr, val);
        range_update(2 * v + 1, mid + 1, r, tl, tr, val);
    }

    void range_update(ll l, ll r, ll val){
        range_update(1, 1, n, l, r, val);
    }

    ll range_query(ll v, ll l, ll r, ll tl, ll tr){
        if (l > r or r < tl or tr > l) return 0;
        if (tl <= l and r <= tr){
            if (tree[v].maximum == 0) return (r - l + 1);
            if (tree[v].minimum > 0) return 0;
            if (l == r){
                return 0;
            }
        }
        ll mid = (l + r) >> 1;
        propogate(v, l, mid, r);
        return range_query(2 * v, l, mid, tl, tr) + range_query(2 * v + 1, mid + 1, r, tl, tr);
    }

    ll range_query(ll l, ll r){
        return range_query(1, 1, n, l, r);
    }
};

void solve(){
    ll n;
    std::cin >> n;

    std::vector<ll> cont[n + 1];
    for (ll i = 1; i <= n; i++){
        cont[i].push_back(0);
    }

    ll a[n + 1];

    for (ll i = 1; i <= n; i++){
        std::cin >> a[i];
        cont[a[i]].push_back(i);
    }

    for (ll i = 1; i <= n; i++){
        cont[i].push_back(n + 1);
    }

    std::vector<std::pair<ll, ll>> start[n + 1];
    std::vector<std::pair<ll, ll>> end[n + 1];

    for (ll i = 1; i <= n; i++){
        if (cont[i].size() <= 2) continue;
        for (ll j = 1; j < cont[i].size() - 1; j++){
            start[cont[i][j - 1] + 1].push_back({cont[i][j], cont[i][j + 1] - 1});
            end[cont[i][j]].push_back({cont[i][j], cont[i][j + 1] - 1});
        }
    }

    std::vector<ll> b(n + 1);
    segment_tree segtree(b);

    ll ans = 0;
    for (ll i = 1; i <= n; i++){
        if (start[i].size()){
            for (auto u: start[i]){
                segtree.range_update(u.first, u.second, 1);
            }
        }

        ans += (n - segtree.range_query(1, n));

        if (end[i].size()){
            for (auto u: end[i]){
                segtree.range_update(u.first, u.second, -1);
            }
        }
    }

    std::cout << ans << '\n';
}

int main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    int t = 1;
    // std::cin >> t;

    while(t--){
        solve();
    }
    return 0;
}