Considerăm un șir de K numere naturale nenule V = (V[1], V[2], V[3], ..., V[K]), unde V[i] reprezintă valoarea elementului din șir aflat pe poziția i (1 ≤ i ≤ 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], ..., A[N]). Numim secvență snake a șirului A o secvență S = (A[L], A[L+1], A[L+2], ..., A[R]) cu 1 ≤ L < R ≤ 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ța

Să se determine câte perechi de poziții (L,R) cu 1 ≤ L < R ≤ N au proprietatea că secvența S = (A[L], A[L+1], A[L+2], ..., 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 ≤ N ≤ 200.000
• 1 ≤ A[i] ≤ 1.000.000.000, 1 ≤ i ≤ N
• Pentru 12 puncte, 1 ≤ N ≤ 300, 1 ≤ A[i] ≤ 20
• Pentru 23 de puncte, 300 < N ≤ 4.000
• Pentru 24 de puncte, 4.000 < N ≤ 200.000, A[i] ≠ A[i+1], 1 ≤ i ≤ N-1
• Pentru 41 de puncte, fără restricții suplimentare

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ă.