== include(page="template/taskheader" task_id="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$.

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

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

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.

h2. Date de iesire

h2. Restrictii

* $1 ≤ N ≤ 1 000 000$
* $0 ≤ K$

* $1 ≤ N ≤ 100 000$

* numerele din sir vor fi mai mici sau egale decat $2^30^$
h2. Exemplu