Les vaches unies de Farmer John (UCFJ) envoient une délégation à l’International bOvine olympIad (IOI).

$N$ vaches participent à la sélection ($1 \leq N \leq 2 \cdot 10^5$). Elles sont alignées, et la vache $i$ est de race $b_i$.

La délégation est un intervalle contigu d’au moins deux vaches : les vaches $l\ldots r$ pour des entiers $l$ et $r$ vérifiant $1\le l<r\le N$. Les deux vaches aux extrémités seront les « chefs ». Pour éviter les conflits au sein d’une race, chaque chef doit être d’une race différente de tous les autres membres, chefs ou non.

Aidez l’UCFJ à déterminer, pour des raisons fiscales, le nombre de façons de choisir une délégation pour l’IOI.

Entrée

La première ligne contient $N$.

La deuxième ligne contient $N$ entiers $b_1,b_2,\ldots,b_N$, chacun dans l’intervalle $[1,N]$.

Sortie

Le nombre de délégations possibles, sur une ligne.

Les grands entiers impliqués peuvent nécessiter un type de 64 bits (par exemple long long en C/C++).

Exemples

Entrée 1

7
1 2 3 4 3 2 5

Sortie 1

13

Remarque

Chaque délégation correspond à l’une des paires de chefs suivantes :

$$(1,2),(1,3),(1,4),(1,7),(2,3),(2,4),(3,4),(4,5),(4,6),(4,7),(5,6),(5,7),(6,7).$$

Sous-tâches

• Les cas 1–3 vérifient $N\le 100$.
• Les cas 4–8 vérifient $N\le 5000$.
• Les cas 9–20 n’ont aucune contrainte supplémentaire.

Crédits du problème : Benjamin Qi