Die vereinten Kühe von Farmer John (UCFJ) schicken eine Delegation zur International bOvine olympIad (IOI).
$N$ Kühe nehmen an der Auswahl teil ($1 \leq N \leq 2 \cdot 10^5$). Sie stehen in einer Reihe, und Kuh $i$ hat Rasse $b_i$.
Die Delegation ist ein zusammenhängendes Intervall von mindestens zwei Kühen: die Kühe $l\ldots r$ für ganze Zahlen $l$ und $r$ mit $1\le l<r\le N$. Die beiden äußersten Kühe werden zu „Anführerinnen“. Um Konflikte innerhalb einer Rasse zu vermeiden, muss jede Anführerin einer anderen Rasse als alle übrigen Delegationsmitglieder angehören, ob Anführerin oder nicht.
Bestimme für UCFJ aus steuerlichen Gründen die Anzahl der Möglichkeiten, eine Delegation zur IOI auszuwählen.
Eingabe
Die erste Zeile enthält $N$.
Die zweite enthält $N$ ganze Zahlen $b_1,b_2,\ldots,b_N$, jeweils im Bereich $[1,N]$.
Ausgabe
Die Anzahl möglicher Delegationen auf einer Zeile.
Die großen Zahlen können 64-Bit-Ganzzahltypen erfordern (zum Beispiel long long in C/C++).
Beispiele
Eingabe 1
7
1 2 3 4 3 2 5Ausgabe 1
13Hinweis
Jede Delegation entspricht einem der folgenden Anführerinnenpaare:
$$(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).$$
Teilaufgaben
- Die Testfälle 1–3 erfüllen $N\le 100$.
- Die Testfälle 4–8 erfüllen $N\le 5000$.
- Die Testfälle 9–20 haben keine zusätzlichen Beschränkungen.
Aufgabenautor: Benjamin Qi