Description

Given a sequence of length $n$, find a contiguous subarray whose average is maximized, with the subarray length $\ge m$.

Input Format

The first line contains two integers $n$ and $m$.
The next $n$ lines each contain an integer $a_i$, representing the $i$-th number of the sequence.

Output Format

Output a single integer: $1000$ times the maximum average. If there is a fractional part, truncate it directly; do not round.

10 6
6
4
2
10
3
8
5
9
4
1

6500

Hint

Constraints

• For $60\%$ of the testdata, it is guaranteed that $m\le n\le 10^4$。
• For $100\%$ of the testdata, it is guaranteed that $1 \leq m\le n\le 10^5$, $0\le a_i\le2000$。

Translated by ChatGPT 5