You are given an array of $n$ integers. For each $i = 1, 2,\dots, n$ , your task is to find the subarray ending at index $i$ with the largest average. If there are multiple subarrays with the largest average, you should find the longest one.
The first line has an integer $n$ : the size of the array.
The next line has $n$ integers $x_1, x_2,\dots, x_n$ : the contents of the array.
Print $n$ integers: the length of the subarray ending at index $i$ with the largest average for each $i = 1, 2,\dots, n$ .
7 1 6 4 6 2 5 5\n · · · · · · \n
1 1 2 1 4 1 2· · · · · · \n
Consider $i = 5$ . The averages of all subarrays ending at index $5$ are $\frac{1 + 6 + 4 + 6 + 2}{5} = 3.8$ , $\frac{6 + 4 + 6 + 2}{4} = 4.5$ , $\frac{4 + 6 + 2}{3} = 4$ , $\frac{6 + 2}{2} = 4$ and $\frac{2}{1} = 2$ . The largest average is $4.5$ and the length of the corresponding subarray is $4$ .