Fișierul intrare/ieșire	suita.in, suita.out	Sursă	Codechef
Autor	Roman Rubanenko	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.05 sec	Limită de memorie	2560 KB
Scorul tău	N/A	Dificultate	2.75

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Suita (clasa a 7-a)

Se dă P, o permutare a numerelor de la 1 la N. P este, deci, un vector de numere distincte două cîte două, cu 1 ≤ P[i] ≤ N pentru orice i.

O suită de lungime K este un subvector ale cărui elemente, după sortare, cresc din 1 in 1. Cu alte cuvinte, dacă avem un subvector P[i..j] de lungime K = j – i + 1, el este suită dacă:

• sortăm crescător subvectorul P[i..j] cu rezultatul în A de K elemente
• A[i] – A[i-1] = 1 pentru orice i (2 ≤ i ≤ K)

Cerință

Găsiți cîte suite de lungime K există în permutarea P.

Date de intrare

Fișierul de intrare suita.in conține pe prima linie numerele N și K. Pe a doua linie conține cele N numere are permutării, despărțite prin spații.

Date de ieșire

În fișierul de ieșire suita.out veți scrie un singur număr, numărul de suite de lungime K din permutarea P.

Restricții

• 1 ≤ N ≤ 400000
• 1 ≤ K ≤ minim dintre 35000 și N
• P[i] distincte două cîte două
• 1 ≤ P[i] ≤ N

Exemplu