Le mucche unite di Farmer John (UCFJ) inviano una delegazione alla International bOvine olympIad (IOI).
$N$ mucche partecipano alla selezione ($1 \leq N \leq 2 \cdot 10^5$). Sono in fila e la mucca $i$ è di razza $b_i$.
La delegazione consiste in un intervallo contiguo di almeno due mucche: le mucche $l\ldots r$ per interi $l$ e $r$ con $1\le l<r\le N$. Le due mucche agli estremi saranno le « leader ». Per evitare conflitti interni alla razza, ogni leader deve avere razza diversa da tutti gli altri membri, leader o meno.
Aiutate UCFJ a determinare, per ragioni fiscali, il numero di modi di scegliere una delegazione per la IOI.
Input
La prima riga contiene $N$.
La seconda contiene $N$ interi $b_1,b_2,\ldots,b_N$, ciascuno nell’intervallo $[1,N]$.
Output
Il numero di delegazioni possibili, su una riga.
I grandi interi possono richiedere tipi a 64 bit (per esempio long long in C/C++).
Esempi
Input 1
7
1 2 3 4 3 2 5Output 1
13Nota
Ogni delegazione corrisponde a una delle seguenti coppie di leader:
$$(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).$$
Sottoproblemi
- I casi 1–3 soddisfano $N\le 100$.
- I casi 4–8 soddisfano $N\le 5000$.
- I casi 9–20 non hanno vincoli aggiuntivi.
Crediti del problema: Benjamin Qi