This page is still under construction.

Parts of this page are still being built. What you see may change.

Maximum Average Segment

Interview

Time limit1sMemory limit64 MB

Summary
Find the largest average over all contiguous subarrays of length at least K and print it truncated to six decimals.
Level

Medium6 of 10

Topics
Binary search, Prefix sum
Solved
No attempts yet

Problem

You are given an array of NN integers. Among all contiguous subarrays whose length is at least KK, find the one with the largest average and report that average.

The average of a subarray is the sum of its elements divided by the number of elements.

Input

The first line contains two integers NN and KK separated by a space (1≤N≤3×1051 \le N \le 3 \times 10^5, 1≤K≤N1 \le K \le N).

The second line contains the array elements a1,a2,…,aNa_1, a_2, \dots, a_N separated by spaces (1≤ai≤1061 \le a_i \le 10^6).

Output

Let AA be the largest possible average. Print AA on one line, truncated to six digits after the decimal point. That is, print ⌊A×106⌋\lfloor A \times 10^6 \rfloor split into an integer part and six decimal digits. Digits past the sixth are cut off, never rounded.

AA is a rational number whose denominator is at most NN, so integer arithmetic computes it exactly. Print all six decimal digits even when they are zeros.

Examples3

  1. Example 1

    Input
    4 1
    1 2 3 4
    
    Expected output
    4.000000
    
  2. Example 2

    Input
    4 2
    2 4 3 4
    
    Expected output
    3.666666
    
  3. Example 3

    Input
    6 3
    7 1 2 1 3 6
    
    Expected output
    3.333333