snake

Considerăm un șir de $K$ numere naturale nenule $V = (V_1, V_2, V_3, \dots, V_K)$, unde $V_i$ reprezintă valoarea elementului din șir aflat pe poziția $i$ ($1 \le i \le K$).

Vom nota cu $compress(V)$ șirul obținut prin înlocuirea tuturor elementelor cu valori egale aflate pe poziții consecutive în șir cu un singur element având acea valoare. De exemplu, dacă $V = (1, 1, 2, 2, 2, 4, 3, 3, 1, 1)$, atunci $compress(V)$ va fi șirul $(1, 2, 4, 3, 1)$.

Spunem că o poziție dintr-un șir este maxim local dacă valoarea de la acea poziție este strict mai mare decât elementele aflate pe pozițiile vecine. Spunem că o poziție dintr-un șir este minim local dacă valoarea de la acea poziție este strict mai mică decât elementele aflate pe pozițiile vecine. Pozițiile de la capetele unui șir cu cel puțin două elemente au un singur vecin. Într-un șir cu un singur element, poziția acestui element este atât minim local, cât și maxim local. De exemplu, pentru șirul $V = (1, 2, 4, 3, 1)$ avem pozițiile $1$ și $5$ ca minime locale, respectiv poziția $3$ ca maxim local, iar pentru $V = (9)$ poziția $1$ este atât minim, cât și maxim local.

Se dă șirul $A$ de $N$ numere naturale nenule $A = (A_1, A_2, A_3, \dots, A_N)$. Numim secvență snake a șirului $A$ o secvență $S = (A_L, A_{L+1}, A_{L+2}, \dots A_R)$ cu $1 \le L < R \le N$ cu proprietatea că fiecare poziție din șirul $compress(S)$ este minim local sau maxim local. De exemplu, pentru șirul $A = (1, 1, 5, 5, 2, 2, 4, 4, 5, 5)$, secvența de la poziția $L = 1$ până la poziția $R = 8$ este snake, deoarece $compress(S) = (1, 5, 2, 4)$.

Cerință

Să se determine câte perechi de poziții $(L, R)$ cu $1 \le L < R \le N$ au proprietatea că secvența $S = (A_L, A_{L+1}, A_{L+2}, \dots A_R)$ este snake.

Date de intrare

Fișierul de intrare snake.in conține două linii. Prima linie conține numărul $N$. A doua linie conține cele $N$ elemente ale șirului $A$, separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire snake.out va conține un singur număr, reprezentând răspunsul la cerință.

Restricții și precizări

• $1 \le N \le 200\ 000$
• $1 \le A_i \le 10^9$, $1 \le i \le N$

Exemplul 1

snake.in

6
1 2 4 4 3 3

snake.out

11

Explicație

Perechile $(L, R)$ care au proprietatea cerută sunt:
$(1, 2)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(2, 6)$, $(3, 4)$, $(3, 5)$, $(3, 6)$, $(4, 5)$, $(4, 6)$, $(5, 6)$.
În total sunt $11$ astfel de perechi.

Exemplul 2

snake.in

7
1 2 4 4 4 5 5

snake.out

14

Explicație

Perechile $(L, R)$ care au proprietatea cerută sunt: $(1, 2)$, $(2, 3)$, $(2, 4)$, $(2, 5)$, $(3, 4)$, $(3, 5)$, $(3, 6)$, $(3, 7)$, $(4, 5)$, $(4, 6)$, $(4, 7)$, $(5, 6)$, $(5, 7)$, $(6, 7)$.
În total sunt $14$ astfel de perechi.

Exemplul 3

snake.in

10
1 1 5 5 2 2 4 4 5 5

snake.out

33

Explicație

Sunt $33$ de perechi $(L, R)$ cu proprietatea cerută.