FMI NO STRESS 13 | yYy

Cerință

Se dă un număr întreg $N$ și o permutare a valorilor de la $0$ la $N-1$. Să se calculeze numărul de secvențe (contigue) de tip deal. O subsecvență $[l, r]$ este considerată deal dacă elementele acesteia respectă una dintre următoarele proprietăți:

• Există o poziție $i$ ($l \leq i \leq r$) astfel încât subsecvența $[l, i]$ este strict crescătoare și subsecvența $[i, r]$ este strict descrescătoare.
• Este fie strict crescătoare, fie strict descrescătoare

Date de intrare

Prima linie conține un număr întreg $N$, reprezentând dimensiunea permutării. A doua linie conține $N$ numere întregi distincte, reprezentând permutarea valorilor de la $0$ la $N-1$.

Date de ieșire

Se va afișa un singur număr întreg, reprezentând numărul total de subsecvențe deal din permutare.

Restricții și precizări

• $1 \leq N \leq 1\ 000\ 000$;
• Permutarea este o aranjare a valorilor de la $0$ la $N-1$, fiecare valoare apare o singură dată;
• Pentru teste în valoare de $20$ de puncte, $N \leq 200$;
• Pentru alte teste în valoare de $30$ de puncte, $N \leq 5\,000$;
• Pentru alte teste în valoare de $50$ de puncte, nu există restricții suplimentare.

Exemplu

stdin

8
7 4 1 2 0 6 5 3

stdout

20

Explicație

Printre subsecvențele deal se numără: $(7); (7, 4, 1); (1, 2, 0); (2); (0, 6); (0, 6, 5, 3)$. În total sunt $20$ de subsecvențe deal.

Un contraexemplu de subsecvență deal este $(4, 1, 2)$.