bete

Se dă $N$ și un șir $a_1, a_2, \dots, a_N$ de numere naturale.
Un tri-băț este o tripletă $(i, j, k)$ cu următoarele proprietăți:

• $1 \leq i < j < k \leq N$
• $a_i = a_{i+1} = \dots = a_{j-1} = a_{j+1} = \dots = a_{k}$
• $a_i \neq a_j$

De exemplu, în șirul $[1, 1, 2, 1, 1, 1, 3, 1, 3, 3]$ câteva tri-bețe sunt: $(2, 3, 4), (1, 3, 4), (1, 3, 5), (5, 7, 8), (7, 8, 10)$.

$(1, 3, 4)$ este tri-băț, deoarece $[a_1, a_2, a_3, a_4] = [1, 1, 2, 1]$. Respectă toate proprietățile.

De asemenea, $(1, 2, 3), (4, 5, 6), (4, 3, 2)$ nu sunt tri-bețe.

Cerință

Se dă $N$ și șirul $a_1, a_2, \dots, a_N$.
Să se afle numărul de tri-bețe din acest șir.

Date de intrare

Pe prima linie a fișierului de intrare bete.in se află numărul $N$.
Pe a doua linie se află șirul $a_1, a_2, \dots, a_N$.

Date de ieșire

Să se afișeze în fișierul bete.out numărul de tri-bețe din șirul $a$.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$;
• $1 \leq a_i \leq N$ pentru fiecare $i$ de la $1$ la $N$.

Exemplu

bete.in

11
1 2 2 2 3 2 2 1 2 1 1

bete.out

10

Explicație

Tri-bețele sunt:
$(2, 5, 6)$; $(2, 5, 7)$; $(3, 5, 6)$; $(3, 5, 7)$; $(4, 5, 6)$; $(4, 5, 7)$; $(6, 8, 9)$; $(7, 8, 9)$; $(8, 9, 10)$; $(8, 9, 11)$.
În total, $10$.