As vacas unidas de Farmer John (UCFJ) enviam uma delegação à International bOvine olympIad (IOI).
$N$ vacas participam da seleção ($1 \leq N \leq 2 \cdot 10^5$). Elas estão em fila e a vaca $i$ tem raça $b_i$.
A delegação consiste em um intervalo contíguo de pelo menos duas vacas: vacas $l\ldots r$ para inteiros $l$ e $r$ satisfazendo $1\le l<r\le N$. As duas vacas das extremidades serão as « líderes ». Para evitar conflitos dentro de uma raça, cada líder deve ter raça diferente de todos os outros membros da delegação, líderes ou não.
Ajude a UCFJ a determinar, por razões tributárias, o número de formas de escolher uma delegação para a IOI.
Entrada
A primeira linha contém $N$.
A segunda contém $N$ inteiros $b_1,b_2,\ldots,b_N$, cada um no intervalo $[1,N]$.
Saída
O número de delegações possíveis, em uma linha.
Os inteiros grandes podem exigir tipos de 64 bits (por exemplo long long em C/C++).
Exemplos
Entrada 1
7
1 2 3 4 3 2 5Saída 1
13Nota
Cada delegação corresponde a um dos seguintes pares 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).$$
Subtarefas
- Os casos 1–3 satisfazem $N\le 100$.
- Os casos 4–8 satisfazem $N\le 5000$.
- Os casos 9–20 não têm restrições adicionais.
Créditos do problema: Benjamin Qi