Las vacas unidas de Farmer John (UCFJ) envían una delegación a la International bOvine olympIad (IOI).
Participan $N$ vacas en la selección ($1 \leq N \leq 2 \cdot 10^5$). Están en fila y la vaca $i$ es de raza $b_i$.
La delegación consiste en un intervalo contiguo de al menos dos vacas: las vacas $l\ldots r$ para enteros $l$ y $r$ que satisfacen $1\le l<r\le N$. Las dos vacas de los extremos serán las « líderes ». Para evitar conflictos entre miembros de la misma raza, cada líder debe tener una raza distinta de todos los demás miembros, sean líderes o no.
Ayuda a UCFJ a determinar, por motivos fiscales, el número de formas de elegir una delegación para la IOI.
Entrada
La primera línea contiene $N$.
La segunda contiene $N$ enteros $b_1,b_2,\ldots,b_N$, cada uno en el rango $[1,N]$.
Salida
El número de delegaciones posibles, en una línea.
Los enteros grandes pueden requerir tipos de 64 bits (por ejemplo long long en C/C++).
Ejemplos
Entrada 1
7
1 2 3 4 3 2 5Salida 1
13Nota
Cada delegación corresponde a una de las siguientes parejas de líderes:
$$(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).$$
Subtareas
- Los casos 1–3 satisfacen $N\le 100$.
- Los casos 4–8 satisfacen $N\le 5000$.
- Los casos 9–20 no tienen restricciones adicionales.
Créditos del problema: Benjamin Qi