Mali Đole je u izlogu prodavnice slatkiša ugledao n bombona. Bombone su poređane u niz i svaka je predstavljena jednim prirodnim brojem - različiti brojevi označavaju da se radi o različitim vrstama bombona, a isti brojevi označavaju iste vrste bombona. On planira da zgrabi neke od bombona, eventualno plati i kasnije se zasladi.

Radi dobitka na brzini, on želi da zgrabi samo neki uzastopni podniz bombona, tj. da izabere indekse i, j (1 ≤ i ≤ j ≤ n) i da pokupi sve bombone koje se nalaze na pozicijama i, i + 1,..., j - 1, j. Takođe, pošto ne voli raznolikost, u tom podnizu ne sme biti više od 3 različite vrste bombona . Npr. podniz 12434 nije dobar jer sadrži 4 vrste bombona.

Odrediti na koliko načina mali Đole može da se zasladi.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza) U prvom redu ulazne datoteke nalazi se jedan prirodan broj n koji predstavlja broj bombona u izlogu (1 ≤ n ≤ 10⁵ ). U sledećem redu se nalaze n prirodnih brojeva (ne većih od 10⁹) koji predstavljaju odgovarajiće vrste bombona.

Izlaz.

(Izlazni podaci se ispisuju na standardni izlaz) U prvom i jedinom redu izlazne datoteke ispisati broj uzastpnih podnizova bombona u kojima se pojavljuju najviše 3 različite vrste.

Primer 1.

5
1 2 4 3 4

13

Objašnjenje. Imamo 13 mogućih podnizova sa traženom osobinom: (12434)(12434) (12434) (12434) (12434) (12434) (12434) (12434) (12434) (12434) (12434) (12434) i (12434)

Primer 2.

6
10 20 10 30 20 20

21

Objašnjenje. Kako ukupno imamo samo 3 različite vrste bombona (10, 20 i 30), svaki uzastopni podniz (a njih ima 21) zadovoljava uslove.

Napomena.
U 20% test primera je n ≤ 100.
U 50% test primera je n ≤ 1000.