Сегмент дужине 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 у низу.

Овај задатак има и другачија решења у делу збирке који следи.