Egy állatkertben egy hosszú, egyirányú sétálóutca egyik oldalán található sorban mind az $N$ állat kifutója. Az állatkert a világon előforduló összes állatfajt egy 1 és ${10}^9$ közötti egyedi (egész) számmal azonosítja. Tudjuk, hogy sorban az $N$ kifutó közül melyikben milyen állat van. Az állatkert speciális túrákat tart. Minden túra résztvevői két tetszőleges kifutó között megtekinthetik az összes állatot. A túra során elengedhetetlen, hogy a látogatók minden, az állatkertben megtalálható állatfajnak legalább egy egyedét láthassák. Az állatkert vezetése kíváncsi, hogy hányféle különböző túrát lehet az állatkertben vezetni ennek a feltételnek a betartásával. Két túra különböző, ha a kezdőpontjuk vagy a végpontjuk különböző. A sétálóutca egyirányú, tehát a résztvevők nem sétálhatnak visszafelé. Készítsünk programot, amely megadja a feltételnek eleget tevő túrák számát.
A standard bemenet első sorában a kifutók $N$ száma van, a következő sor tartalmazza a kifutók ,,lakóinak'' azonosítóját sorrendben.
A standard kimenet egyetlen egész számot tartalmazzon: a különböző túrák számát.
Pontozás: Az első két tesztesetben $N\le 100$, a harmadik tesztesetben $N\le 5000$.
Korlátok: $1\le N\le 2\cdot {10}^5$, minden állatfaj azonosítója 1 és ${10}^9$ közötti egész, az időkorlát 1 mp.