Question
Subarray with least average
Given an array arr of size n, Find the subarray with the least average of size k.
Find the index of the first element of the subarray (1-based indexing) of size k that has the least average.
If multiple subarrays have the same average then return the subarray with a lower index.
Find the index of the first element of the subarray (1-based indexing) of size k that has the least average.
If multiple subarrays have the same average then return the subarray with a lower index.
Input
The first line of input will take two space-separated integers representing n and k respectively.
The next line of input will take n space-separated integers representing elements of array arr.
Constraints:
1 ≤ k ≤ n ≤ 105
1 ≤ elements of array ≤ 106
The next line of input will take n space-separated integers representing elements of array arr.
Constraints:
1 ≤ k ≤ n ≤ 105
1 ≤ elements of array ≤ 106
Output
Print a single integer representing the index of the first element of the subarray(1-based indexing) of size k that has the lowest average.
Example
Input:
3 1
30 20 10
Output:
3
Explanation:
Subarrays of length 1 are {30}, {20}, {10}. {10} has the least average.
Input:
3 2
30 20 10
Output:
2
Explanation:
Subarrays of length 2 are {30, 20}, {20, 10}. {20, 10} has the least average.
3 1
30 20 10
Output:
3
Explanation:
Subarrays of length 1 are {30}, {20}, {10}. {10} has the least average.
Input:
3 2
30 20 10
Output:
2
Explanation:
Subarrays of length 2 are {30, 20}, {20, 10}. {20, 10} has the least average.