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

Explicatie

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

Cum se trimit solutii?