Maximum Average Subarray

You are given an array of integers and an integer k. Your task is to find the contiguous subarray of length k that has the maximum sum and then compute its average. Formally, given an array A = [a₁, a₂, ..., a_n] and an integer k, you need to find

$$ \max_{1 \leq i \leq n-k+1} \frac{a_i + a_{i+1} + \cdots + a_{i+k-1}}{k} $$

and output the maximum average. It is guaranteed that 1 ≤ k ≤ n.

Examples:

• For A = [1, 12, -5, -6, 50, 3] and k = 4, the maximum average is 12.75.
• For A = [5, 5, 5, 5, 5, 5, 5] and k = 3, the maximum average is 5.0.
• For A = [1, 2, 3, 4, 5, 6] and k = 2, the maximum average is 5.5.

inputFormat

The input is given via stdin and it consists of three parts:

1. An integer n representing the number of elements in the array.
2. A line with n space-separated integers representing the array elements.
3. An integer k representing the length of the subarray.

For example:

6
1 12 -5 -6 50 3
4

outputFormat

Output the maximum average (a floating-point number) of any contiguous subarray of length k to stdout.

## sample

6
1 12 -5 -6 50 3
4

12.75