Problem 4425: altern

Cerință

Se dă un o permutare de lungime $n$ (un șir cu $n$ elemente care conține toate numerele de la $1$ la $n$ așezate într-o ordine oarecare). Numim segment monoton o secvență (elemente așezate pe poziții consecutive), în care valorile sunt fie în ordine crescătoare, fie în ordine descrescătoare, și care este totodată maximală (adică dacă am mai extinde secvența, aceasta și-ar pierde monotonia). De exemplu șirul $1\ 2\ 3\ 5\ 4\ 6$ are $3$ segmente monotone: $[1,\ 2,\ 3,\ 5]$ , $[5,\ 4]$ și $[4,\ 6]$ .
Avem voie să aplicăm o singură dată asupra șirului o operație de oglindire a unei secvențe date (ne alegem noi ce secvență dorim să oglindim). Determinați câte șiruri distincte cu exact $k$ segmente monotone se pot obține (aplicând deci o singură dată operația de oglindire asupra șirului original).

Date de intrare

Pe prima linie a fisierului altern.in se află numărul $n$ , pe a doua linie se află $n$ valori naturale distincte de la $1$ la $n$ , separate prin spațiu, iar pe a treia linie se află valoarea $k$ .

Date de ieșire

Fișierul altern.out conține pe prima linie numărul de șiruri cu proprietatea cerută.

Restricții și precizări

$2 \leq n \leq 2000$
$1 \leq k \leq n$
Secvența oglindită trebuie să fie formată din cel puțin două elemente.
Pentru 30 de puncte $2 \leq n \leq 100$
Pentru alte 70 de puncte $100 \lt n \leq 2000$

Exemplu

altern.in

6
1 2 3 5 4 6
4

altern.out

Explicație

Mai jos considerăm termenii șirului numerotați de la $1$ .
Aplicând oglindire pe secvența cu capetele în indicii $1$ și $2$ , obtinem sirul $2\ 1\ 3\ 5\ 4\ 6$
Aplicând oglindire pe secvența cu capetele în indicii $1$ și $3$ , obtinem sirul $3\ 2\ 1\ 5\ 4\ 6$
Aplicând oglindire pe secvența cu capetele în indicii $2$ și $6$ , obtinem sirul $1\ 6\ 4\ 5\ 3\ 2$
Aplicând oglindire pe secvența cu capetele în indicii $3$ și $6$ , obtinem sirul $1\ 2\ 6\ 4\ 5\ 3$
Fiecare dintre cele $4$ șiruri obținute mai sus are cate $4$ segmente monotone.
Pentru o mai bună înțelegere a modului în care se realizează operația de oglindire și se calculează numărul de segmente monotone, în tabelul următor sunt exemplificate toate oglindirile posibile, precum și numărul de secvențe căutate pentru șirul din exemplul dat anterior.

Indicele de start al secvenței oglindite	Indicele de final al secvenței oglindite	Șirul după oglindire	Numărul de segmente monotone din șir
$1$	$2$	$2$ $1$ $3$ $5$ $4$ $6$	$4$
$1$	$3$	$3$ $2$ $1$ $5$ $4$ $6$	$4$
$1$	$4$	$5$ $3$ $2$ $1$ $4$ $6$	$2$
$1$	$5$	$4$ $5$ $3$ $2$ $1$ $6$	$3$
$1$	$6$	$6$ $4$ $5$ $3$ $2$ $1$	$3$
$2$	$3$	$1$ $3$ $2$ $5$ $4$ $6$	$5$
$2$	$4$	$1$ $5$ $3$ $2$ $4$ $6$	$3$
$2$	$5$	$1$ $4$ $5$ $3$ $2$ $6$	$3$
$2$	$6$	$1$ $6$ $4$ $5$ $3$ $2$	$4$
$3$	$4$	$1$ $2$ $5$ $3$ $4$ $6$	$3$
$3$	$5$	$1$ $2$ $4$ $5$ $3$ $6$	$3$
$3$	$6$	$1$ $2$ $6$ $4$ $5$ $3$	$4$
$4$	$5$	$1$ $2$ $3$ $4$ $5$ $6$	$1$
$4$	$6$	$1$ $2$ $3$ $6$ $4$ $5$	$3$
$5$	$6$	$1$ $2$ $3$ $5$ $6$ $4$	$2$

altern