FMI NO STRESS 13 | yYy

This was the problem page during the contest. Access the current page here.
Time limit: 1s Memory limit: 256MB Input: Output:

Cerință

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

  • Există o poziție ii (lirl \leq i \leq r) astfel încât subsecvența [l,i][l, i] este strict crescătoare și subsecvența [i,r][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 NN, reprezentând dimensiunea permutării. A doua linie conține NN numere întregi distincte, reprezentând permutarea valorilor de la 00 la N1N-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

  • 1N1 000 0001 \leq N \leq 1\ 000\ 000;
  • Permutarea este o aranjare a valorilor de la 00 la N1N-1, fiecare valoare apare o singură dată;
  • Pentru teste în valoare de 2020 de puncte, N200N \leq 200;
  • Pentru alte teste în valoare de 3030 de puncte, N5000N \leq 5\,000;
  • Pentru alte teste în valoare de 5050 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)(7); (7, 4, 1); (1, 2, 0); (2); (0, 6); (0, 6, 5, 3). În total sunt 2020 de subsecvențe deal.

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

Log in or sign up to be able to send submissions!