Task

You are given a positive integer array arr, and an integer k.

Your task is to find the maximum mean value that calculated by AT LEAST k continuous elements.

The output should be a string. If the result is not an integer, returns the fractional form such as "10/3", "11/2", etc.. Otherwise, returns the integer in string format.

Note, If the fractional form can be simplified, you need to simplify it. For example: "10/4" can be simplified to "5/2", 28/8 can be simplified to "7/2".

Note

• 2 <= arr.length <= 50000, 2 <= k <= arr.length, 1 <= arr[i] <= 100

• 3 fixed testcases

• 100 random testcases, testing for correctness of solution

• 100 random testcases, testing for performance of code

• All inputs are valid.

• Pay attention to code performance.

• If my reference solution gives the wrong result in the random tests, please let me know(post an issue).

Example

For arr=[1,2,3,4,5], k=2, the output should be "9/2".

All possible mean values are:

(1+2)/2 = 3/2
(1+2+3)/3 = 2
(1+2+3+4)/4 = 10/4 = 5/2
(1+2+3+4+5)/5 = 3
(2+3)/2 = 5/2
(2+3+4)/3 = 3
(2+3+4+5)/4 = 7/2
(3+4)/2 = 7/2
(3+4+5)/3 = 4
(4+5)/2 = 9/2

"9/2" is the largest one.

For arr=[1,2,3,4,5], k=3, the output should be "4".

All possible mean values are:

(1+2+3)/3 = 2
(1+2+3+4)/4 = 10/4 = 5/2
(1+2+3+4+5)/5 = 3
(2+3+4)/3 = 3
(2+3+4+5)/4 = 7/2
(3+4+5)/3 = 4

"4" is the largest one.

For arr=[1,8,2,4,8], k=3, the output should be "11/2".

(8+2+4+8)/4 = 22/4 = 11/2