Fişierul intrare/ieşire:	mmsir.in, mmsir.out	Sursă	Autumn Warmup 2007, Runda 2
Autor	Tiberiu Savin	Adăugată de	Savin Tiberiu •devilkind
Timp execuţie pe test	0.225 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

MMsir

Se da un sir cu N elemente distincte. Definim gradul unui sir ca fiind numarul de schimbari de monotonie ale acestuia. Numarul de schimbari de monotonie ale unui sir cu N elemente reprezinta numarul de pozitii i ($1 < i < N$) cu propietatea ca a[i-1]<$a[i]$>$a[i+1]$ sau a[i-1]>$a[i]$<$a[i+1]$. Se cere sa se gaseasca numarul de subsecvente ale sirului cu gradul &k&.

Date de intrare

Pe prima linie a fisierului mmsir.in se vor afla 2 numere reprezentand numerele n si m. Pe a doua linie se vor afla n numere reprezentand sirul.

Date de iesire

In fisierul mmsir.out se va afla un singur numar, rezultatul cerut in enunt.

Restrictii

• $ 1 ≤ n ≤ 100 000$
• numerele din sir vor fi mai mici sau egale decat 2³⁰

Exemplu

table(example). |_. mmsir.in |_. mmsir.out |
|
6 2
1 2 0 4 6 5
|
3
|

Explicatie

Cele trei subsecvente au capetele 1 4, 1 5 si 2 5

Cum se trimit solutii?