Description

Given a sequence $a$ of length $n$, where $a_i$ is the value of the $i$-th element. You need to find the most valuable "segment" in the sequence. A segment is a contiguous subsequence whose length is in $[S, T]$. The most valuable segment is the one with the maximum average value.

The average value of a segment equals the total value of the segment divided by the segment length.

Input Format

The first line contains an integer $n$, the length of the sequence.

The second line contains two integers $S$ and $T$, the allowed range of the segment length, i.e., in $[S, T]$.

From the 3rd line to line $n+2$, each line contains one integer, the value of each element.

Output Format

Output a real number with $3$ decimal places, representing the average value of the optimal segment.

3
2 2
3
-1
2

1.000

Hint

Constraints

• For $30\%$ of the testdata, $n \le 1000$.
• For $100\%$ of the testdata, $1 \le n \le 100000$, $1 \le S \le T \le n$, $-{10}^4 \le a_i \le {10}^4$.

Source

• Adapted by tinylic.

Translated by ChatGPT 5