== 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

h2. Restrictii
* $ 1 ≤ n ≤ 100 000$

* numerele din sir vor fi mai mici sau egale decat 2^30^

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

h2. Exemplu
table(example). |_. mmsir.in |_. mmsir.out |

|
6 2

| 6 2

1 2 0 4 6 5

|
3

| 3

|
h3. Explicatie