// supersegments, O(n*sqrt(n)), by Errichto
#include<bits/stdc++.h>
using namespace std;

const int nax = 1e6 + 5;
int n;
#define inf (n+1)
int t[nax]; // input
int tmp[nax];
int nxt[nax]; // nxt[i] = index of the next occurrence of number t[i]
int at_least[nax]; // at_least[i] = the lowest possible index j that interval [i, j] has enough occurrences of number t[i]

void calculate_nxt() {
    for(int i = 1; i <= n; ++i) tmp[i] = inf;
    for(int i = n; i >= 1; --i) {
        nxt[i] = tmp[t[i]];
        tmp[t[i]] = i;
    }
    // nxt[inf] = inf; // necessary or not? I'm not sure
}

void calculate_at_least() {
    for(int i = 1; i <= n; ++i) tmp[i] = 0;
    for(int i = 1; i <= n; ++i) {
        int x = t[i];
        if(tmp[x] != 0) { // here is the first occurrence of number x
            tmp[x] = nxt[tmp[x]];
            at_least[i] = tmp[x];
        }
        else {
            tmp[x] = i;
            for(int rep = 0; rep < x - 1 && tmp[x] != inf; ++rep)
                tmp[x] = nxt[tmp[x]];
            at_least[i] = tmp[x];
        }
    }
}

int main() {
    freopen("segments.in", "r", stdin);
    freopen("segments.out", "w", stdout);

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &t[i]);
    calculate_nxt();
    calculate_at_least();

    set<int> first_occurrences;
    long long ans = 0;
    for(int A = n; A >= 1; --A) {
        if(nxt[A] != inf) first_occurrences.erase(nxt[A]);
        first_occurrences.insert(A);
        set<int> :: iterator it = first_occurrences.begin();
        int minB = A; // the minimum index of endpoint B; I increase it when I encounter a new number x - then I must move it to get at least x occurrences of x
        int maxB = n; // the maximum index of endpoing B; I decrease it when I encounter a new number x - I can't get at least x+1 occurrences
        while(it != first_occurrences.end()) {
            int needed = at_least[*it];
            if(needed == inf) break;
            minB = max(minB, needed);
            maxB = min(maxB, nxt[needed] - 1);
            if(minB > maxB) break;
            ++it;
            if(it == first_occurrences.end() || minB < *it) ++ans;
        }
    }
    printf("%lld\n", ans);
    return 0;
}