Сегмент дужине k највећег просека

Овај задатак је поновљен у циљу увежбавања различитих техника решавања.

Дат је низ $a$ реалних бројева дужине $n$ и природан број $k$. Написати програм којим се у низу $a$ одређује позиција почетка сегмента (подниза узастопних елемената) дужине $k$ са највећим просеком (ако више сегмената има исти просек, пријавити последњи од њих).

Улаз

У првој линији стандардног улаза налази се природан број $k$ ($k\leq 5 \cdot 10^3$). У другој линији налази се природан број $n$ ($n \leq 5\cdot 10^5$). У следећих $n$ линија налазе се по један реалан број (ти бројеви представљају редом елементе низа $a$).

Излаз

На стандарном излазу приказати позицију почетка последњег сегмента дужине $k$ низа $a$ чији је просек највећи (позиције у низу се броје од нуле).

Пример

Улаз

3
5
1.0
5.0
8.0
2.0
7.0

Излаз

2

Сегмент највећег просека је 8, 2, 7 и он почиње на позицији 2 у низу.