Zadanie

Huncút Hugo

Počet bodov: 50, časový limit: 2000ms

Hugova suseda, teta Hedviga, má na záhrade v rade \(n\) trpaslíkov. Hugo, ktorý sa v skutočnosti volá Denis, je huncút a postrach okolia, a každý deň vyvedie Hedvige beťárstvo. Denis sa v noci vkradne na jej záhradu, vyberie si \(k\) za sebou idúcich trpaslíkov a usporiada ich podľa výšky od najnižšieho po najvyššieho. Každé ráno to Hedviga zistí, najeduje sa (aj ak sa Hugovim činom poradie nezmení), a napraví ich späť do pôvodného poradia. Denis však nikdy neopakuje svoje gagy (dva gagy považujeme za rovnaké ak poradie trpaslíkov po ich vykonaní je rovnaké). Koľko najviac dní môže Hugo robiť svoje viťúzstva?

Vstup a výstup

Na prvom riadku sú čísla \(n\) a \(k\). Platí \(1 \leq k \leq n \leq 500\,000\). Na druhom riadku je \(n\) čísel oddelených medzerou: nejaká permutácia čísel \(1\) až \(n\).

Na výstup vypíšte jedno číslo: koľko rôznych permutácií môžme dostať zo zadanej permutácie tým, že utriedime nejaký súvislý úsek dĺžky \(k\) od najmenšieho po najväčší.

Príklady

Input:

5 3
1 4 2 5 3

Output:

2

Môžme dostať (1, 2, 4, 5, 3) a (1, 4, 2, 3, 5).

Input:

9 6
9 8 7 6 5 4 3 2 1

Output:

4

Máme štyri možnosti ktorý úsek utriediť, pre každú dostaneme niečo iné.