Povprečje

Podan je seznam $N$ celih števil $X_1, \ldots, X_N$. V njem iščemo strnjen podseznam $X_l, X_{l+1}, \ldots, X_r$ dolžine vsaj $K$ elementov ($r-l+1 \geq K$), ki ima največje (navzdol zaokroženo) povprečje $f(l,r) = \left \lfloor \frac{X_l + X_{l+1} + \ldots + X_r}{r-l+1} \right \rfloor$.

Omejitve podatkov:

• $1 \leq K \leq N \leq 10^6$
• $0 \leq X_i \leq 10^9$

Vhodni in izhodni podatki:

V prvi vrstici sta podani števili $N$ in $K$, v drugi vrstici pa sledi seznam $N$ celih števil $X_i$, ki so med seboj ločena s presledkom.

Izpišite iskano največje povprečje $f(l,r)$ pri pogoju $r-l+1 \geq K$.

Primer vhoda:

20 6
18 3 16 14 7 4 15 11 10 12 2 17 9 1 19 13 5 20 8 6

Pravilen izhod:

12

Strnjen podseznam števil 17, 9, 1, 19, 13, 5, 20 ima povprečje 12.