Problem Description

Original problem from: USACO 2003 Mar. Green.

Given a non-negative integer sequence $A$ of length $n$, find a subarray with the maximum average value, with length at least $L$.

Input Format

The first line contains two integers $n$ and $L$, separated by spaces.

The second line contains $n$ non-negative integers separated by spaces, representing $A_i$.

Output Format

Output one integer, which is $1000$ times this maximum average. Do not round; output it directly.

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

6500

Hint

Constraints: $1 \leq n \leq 10^5,0 \leq A_i \leq 2000$。

Translated by ChatGPT 5