Se consideră un şir a₁, a₂, ..., a_N de numere întregi şi L un număr natural. O secvenţă din acest şir a_i, a_i+1, ..., a_i+2L de lungime 2*L+1 spunem că este echilibrată, dacă elementul a_i+Ldin mijloc are în restul secvenţei exact L elemente strict mai mici decât el şi exact L elemente mai mari sau egale cu el. De exemplu, pentru şirul 7, 3, 8, 7, 5, 1, 7, 4, 8, 8, 9 şi L=3, sunt trei astfel de secvenţe: prima, 7, 3, 8, 7, 5, 1, 7, a doua 3, 8, 7, 5, 1, 7, 4 şi a treia 7, 5, 1, 7, 4, 8, 8.

Cerinţă

Scrieţi un program care să determine numărul de secvenţe echilibrate de lungime 2*L+1 din şir.

Date de intrare

Fişierul de intrare echilibru1.in conţine pe prima linie două numere naturale N şi L. Pe linia a doua se găsesc cele N elemente ale şirului, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire echilibru1.out va conţine un singur număr natural reprezentând numărul de secvenţe echilibrate de lungime 2*L+1 din şir.

Restricţii

• 1 <= N <= 800 000
• -500 000 < a_i < 500 000, pentru orice 1 <= i <= N.
• 1 <= L < N div 2

Exemplu

echilibru1.in	echilibru1.out
11 3 7 3 8 7 5 1 7 4 8 8 9	3

prof. Dan Pracsiu

Grupul Şcolar „Ştefan Procopiu” Vaslui

dpracsiu@yahoo.com