#include <bits/stdc++.h>   using namespace std;   const int N = 5e5 + 10;   unsigned long long x[N], y[N], f[N];   int a[N], cnt[N];   queue<int> g[N];   mt19937_64 rng(time(0));   char buf[1 << 23], *p1 = buf, *p2 = buf, obuf[1 << 23], *O = obuf;   inline int rd() {     int x = 0, f = 1;     char ch =         (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)              ? EOF              : *p1++);     while (!isdigit(ch)) {       if (ch ==  - ) f = -1;       ch =           (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)                ? EOF                : *p1++);     }     while (isdigit(ch))       x = x * 10 + (ch ^ 48),       ch =           (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)                ? EOF                : *p1++);     return x * f;   }   namespace Hash {   const int hashmod = 999983;   int v[hashmod];   bool vis[hashmod];   unsigned long long h[hashmod];   int &get(unsigned long long S) {     int i = S % hashmod;     for (; vis[i] && h[i] != S; i = (i + 1) % hashmod)       ;     if (!vis[i]) vis[i] = 1, h[i] = S;     return v[i];   }   }  // namespace Hash   int main() {     int n = rd();     for (int i = 1; i <= n; ++i) {       a[i] = rd();       x[i] = rng();       y[i] = rng();     }     unsigned long long now = 0, ans = 0;     ++Hash::get(now);     int p = 0;     for (int i = 1; i <= n; ++i) {       if (g[a[i]].size() == 3) {         int t = g[a[i]].front();         g[a[i]].pop();         while (p < t) --Hash::get(f[p++]);       }       g[a[i]].push(i);       switch (++cnt[a[i]] % 3) {         case 1:           f[i] = now ^= x[a[i]];           break;         case 2:           f[i] = now ^= y[a[i]];           break;         case 0:           f[i] = now ^= x[a[i]] ^ y[a[i]];           break;       }       ans += Hash::get(now)++;     }     printf( %lld n , ans);   }   