Furnicuțe

În Împărăția Roșie există un șir de $N$ dale, pe fiecare aflându-se un anumit număr de boabe de mei. Împăratul Roșu i-a dat o nouă sarcină lui Harap-Alb: acesta îi spune eroului că își va alege un număr, $R$, iar Harap-Alb trebuie să îi dea un segment de dale, de lungime $2 \cdot R + 1$ care au aceeași cantitate de boabe de mei. Eroul știe că poate apela la Regina Furnicilor ca să își trimită supusele să execute sarcina, însă dorește să se folosească de cât mai puține furnicuțe, ca să nu le obosească. Știm că o furnicuță poate căra un singur bob de mei, pe care îl va duce direct în mușuroi (nu pe alte dale) și că ea îl va ajuta pe Harap-Alb doar la eliminarea unui singur bob de mei de pe dală (ca să nu obosească).

Cerință

Ajutați-l pe Harap-Alb să îndeplinească sarcina dată de Împăratul Roșu, folosind cât mai puține furnicuțe.

Date de intrare

Din fișierul de intrare furnici.in se citesc, în ordine, $N$, $R$ și apoi $N$ valori numere naturale, reprezentând cantitatea de boabe de mei de pe fiecare dală.

Date de ieșire

În fișierul de ieșire, furnici.out se va scrie un singur număr natural, reprezentând indicele la care începe segmentul de lungime cerută. În cazul în care există mai multe soluții se va afișa cea cu indicele minim.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• O dală poate conține între $1$ și $99 \ 999 \ 999$ boabe de mei;
• $3 \leq 2 \cdot R + 1 \leq N$;
• Pentru 30 de puncte, $N \leq 5000$;
• Pentru alte 70 de puncte, nu există restricții suplimentare.

Exemplul 1

furnici.in

7 2
5 1 3 12 6 4 3

furnici.out

3

Explicație

Dacă aleg segmentul care începe la poziția $1$, de lungime $5$, se folosesc $22$ de furnicuțe, dacă aleg segmentul ce începe la poziția $2$, se folosesc $21$ de furnicuțe, iar dacă aleg segmentul ce începe la poziția $3$, se folosesc $13$ furnicuțe. Observăm că numărul minim de furnicuțe este utilizat de segmentul care începe pe poziția $3$.

Exemplul 2

furnici.in

6 1
2 1 2 1 2 1

furnici.out

2

Explicație

Numărul cel mai mic de furnicuțe, $1$, se obține alegând segmentul de lungime $3$ care începe pe poziția $2$ sau pe poziția $4$. Deoarece ne interesează cel mai mic indice, în fișierul de ieșire se va scrie $2$.