Given an array Arr of size N and a positive integer K, find the sub-array of length K with the maximum average. 
Example 1:
Input:
K = 4, N = 6
Arr[] = {1, 12, -5, -6, 50, 3}
Output: 12 -5 -6 50
Explanation: Maximum average is 
(12 - 5 - 6 + 50)/4 = 51/4.
Example 2:
Input:
K = 3, N = 7
Arr[] = {3, -435, 335, 10, -50, 100, 20}
Output: 335 10 -50
Explanation: Maximum average is 
(335 + 10 - 50)/3 = 295/3.
Your Task:
You don't need to read input or print anything. Your task is to complete the function findMaxAverage() which takes the array of integers arr, its size n and integer k as input parameters and returns an integer denoting the starting index of the subarray.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints
1 <= N <= 10^{5}
0 <= |Arr[i]| <= 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def findMaxAverage(self, arr, n, k):

        # code here

Solutions:
class Solution:

	def findMaxAverage(self, arr, n, k):
		st = 0
		ed = k - 1
		cur = 0
		for i in range(k):
			cur += arr[i]
		ma = cur
		for i in range(k, n):
			cur += arr[i]
			cur -= arr[i - k]
			if ma < cur:
				ma = cur
				st = i - k + 1
				ed = i
		return st


class Solution:

	def findMaxAverage(self, arr, n, k):
		i = j = s = 0
		fi = li = 0
		for i in range(k):
			s += arr[i]
		mx = s
		j = k
		i = 1
		while j < n:
			s -= arr[i - 1]
			s += arr[j]
			if mx < s:
				mx = s
				fi = i
			i += 1
			j += 1
		return fi


class Solution:

	def findMaxAverage(self, arr, n, k):
		if k >= n:
			return 0
		s = sum(arr[:k])
		t = s
		j = 0
		l = 0
		for i in range(k, n):
			t += arr[i]
			t -= arr[l]
			l += 1
			if t > s:
				s = t
				j = l
		return j


class Solution:

	def findMaxAverage(self, arr, n, k):
		Sum = 0
		mx = float('-inf')
		start = 0
		idx = 0
		for end in range(len(arr)):
			Sum += arr[end]
			if end >= k - 1:
				if mx < Sum:
					mx = Sum
					idx = start
				Sum -= arr[start]
				start += 1
		return idx


class Solution:

	def findMaxAverage(self, arr, n, k):
		summ = sum(arr[0:k])
		index = 0
		maxsum = sum(arr[0:k])
		for i in range(k, n):
			summ += arr[i] - arr[i - k]
			if summ > maxsum:
				maxsum = summ
				index = i - k + 1
		return index


class Solution:

	def findMaxAverage(self, arr, n, k):
		maxi = -1e+19
		i = 0
		sum = 0
		while i < k:
			sum += arr[i]
			i += 1
		maxi = max(maxi, sum)
		start = 0
		while i < n:
			sum += arr[i] - arr[i - k]
			if maxi < sum:
				maxi = sum
				start = i - k + 1
			i += 1
		return start


class Solution:

	def findMaxAverage(self, arr, n, k):
		summa = sum(arr[:k])
		maxi = summa
		index = 0
		for i in range(n - k):
			summa += arr[i + k] - arr[i]
			if summa > maxi:
				maxi = summa
				index = i + 1
		return index


class Solution:

	def findMaxAverage(self, arr, n, k):
		i = 0
		j = 0
		_sum = 0
		_max = -float('inf')
		idx = 0
		while j < n:
			_sum += arr[j]
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if _max < _sum:
					_max = _sum
					idx = i
				_sum -= arr[i]
				i += 1
				j += 1
		return idx


class Solution:

	def findMaxAverage(self, arr, n, k):
		idx = 0
		sum1 = sum(arr[:k])
		maxsum = sum1
		for i in range(k, n):
			sum1 += arr[i] - arr[i - k]
			if sum1 > maxsum:
				maxsum = sum1
				idx = i - k + 1
		return idx


class Solution:

	def findMaxAverage(self, arr, n, k):
		maxi = -float('inf')
		start = 0
		su = 0
		for i in range(k):
			su += arr[i]
		if su / k > maxi:
			maxi = su / k
			start = 0
		for i in range(k, n):
			su -= arr[i - k]
			su += arr[i]
			if su / k > maxi:
				maxi = su / k
				start = i - k + 1
		return start


import numpy as np

class Solution:

	def findMaxAverage(self, arr, n, k):
		x = 0
		sum1 = sum(arr[:k])
		maxsum = sum1
		for i in range(k, n):
			sum1 += arr[i] - arr[i - k]
			if sum1 > maxsum:
				maxsum = sum1
				x = i - k + 1
		return x


class Solution:

	def findMaxAverage(self, arr, n, k):
		start = 0
		end = start
		max_sum = float('-inf')
		curr_sum = 0
		ans = start
		while end < n:
			curr_sum += arr[end]
			if end - start + 1 == k:
				if max_sum < curr_sum:
					ans = start
					max_sum = curr_sum
				curr_sum -= arr[start]
				start += 1
			end += 1
		return ans


import math

class Solution:

	def findMaxAverage(self, arr, n, k):
		sum = 0
		idx = 0
		maxsum = 0
		for i in range(k):
			sum += arr[i]
		maxsum = sum
		for j in range(k, n):
			sum += arr[j] - arr[j - k]
			if sum > maxsum:
				maxsum = sum
				idx = j - k + 1
		return idx


class Solution:

	def findMaxAverage(self, arr, n, k):
		s = 0
		res = []
		add = 0
		maxi = float('-inf')
		idx = 0
		for l in range(n):
			add += arr[l]
			if l >= k - 1:
				if maxi < add:
					maxi = add
					idx = s
				add -= arr[s]
				s += 1
		return idx


class Solution:

	def findMaxAverage(self, arr, n, k):
		s = sum(arr[0:k])
		gm = s
		a = 0
		for i in range(n - k):
			s -= arr[i]
			s += arr[k + i]
			if s > gm:
				a = i + 1
				gm = s
		return a


class Solution:

	def findMaxAverage(self, arr, n, k):
		mx = -9999999
		Sum = 0
		for i in range(k):
			Sum += arr[i]
		ind = 0
		mx = max(mx, Sum)
		for i in range(n - k):
			Sum -= arr[i]
			Sum += arr[k + i]
			if Sum > mx:
				ind = i + 1
				mx = Sum
		return ind


class Solution:

	def findMaxAverage(self, arr, n, k):
		l = 0
		r = k
		s = arr[l:r]
		su = sum(s)
		maxi = su / k
		start = l
		end = r
		while r < n:
			su = su - arr[l]
			l = l + 1
			su = su + arr[r]
			r = r + 1
			res = su / k
			if res > maxi:
				start = l
				end = r
				maxi = res
		return start


class Solution:

	def findMaxAverage(self, arr, n, k):
		answer = []
		sum = 0
		i = 0
		ans = 0
		j = 0
		nums = arr
		while i <= k - 1:
			sum = sum + nums[i] / k
			i += 1
		temp = sum
		while j < len(nums) - k:
			sum = sum - nums[j] / k + nums[j + k] / k
			j += 1
			if sum > temp:
				temp = sum
				ans = j
		return ans


class Solution:

	def findMaxAverage(self, arr, n, k):
		ans = 0
		ma = sum(arr[0:k])
		ma2 = sum(arr[0:k])
		if k > n:
			return -1
		for i in range(1, n - k + 1):
			ma1 = ma - arr[i - 1] + arr[i - 1 + k]
			ma2 = max(ma2, ma1)
			if ma2 == ma1:
				ans = i
			ma = ma1
		return ans


class Solution:

	def findMaxAverage(self, arr, n, k):
		l = 0
		j = 0
		mx_i = 0
		mx_j = 0
		add = 0
		avg = 0
		mx_avg = 0
		for i in range(k):
			add += arr[i]
			j = i
		mx_j = j
		avg = mx_avg = add / k
		for i in range(k, n):
			add -= arr[l]
			l += 1
			add += arr[i]
			avg = add / k
			if avg > mx_avg:
				mx_avg = avg
				mx_i = l
				mx_j = i
		return mx_i


import math

class Solution:

	def findMaxAverage(self, arr, n, k):
		i = 0
		j = 0
		sum = 0
		ans = -math.inf
		idx = 0
		while j < n:
			sum += arr[j]
			if j - i + 1 < k:
				j += 1
			else:
				x = sum / k
				if x > ans:
					ans = x
					idx = i
				sum -= arr[i]
				i += 1
				j += 1
		return idx


class Solution:

	def findMaxAverage(self, nums, n, k):
		i = 0
		j = 0
		s = 0.0
		y = n + 1
		ma = sum(nums[:k]) / k
		if len(nums) == 1:
			return nums[0] / 1
		while j < len(nums):
			s = s + nums[j]
			if j - i + 1 < k:
				j = j + 1
			elif j - i + 1 == k:
				t = s / k
				if t > ma:
					ma = t
					y = i
				s = s - nums[i]
				i = i + 1
				j = j + 1
		if y == n + 1:
			return 0
		else:
			return y


class Solution:

	def findMaxAverage(self, arr, n, k):
		sum = 0
		for i in range(k):
			sum += arr[i]
		max = sum / k
		ind = 0
		l = k
		r = 0
		while l < n:
			sum = sum + arr[l] - arr[r]
			l += 1
			r += 1
			if max < sum / k:
				ind = r
				max = sum / k
		return ind


class Solution:

	def findMaxAverage(self, arr, n, k):
		i = 0
		fans = 0
		s = 0
		for j in range(k):
			s = s + arr[j]
			fans = i
		ans = s
		while j < len(arr) - 1:
			j = j + 1
			s = s - arr[i] + arr[j]
			if s > ans:
				ans = s
				fans = i + 1
			i = i + 1
		return fans


class Solution:

	def findMaxAverage(self, arr, n, k):
		m = 0
		s = 0
		for i in range(k):
			s += arr[i]
		h = s
		for i in range(k, n):
			s -= arr[i - k]
			s += arr[i]
			if s > h:
				h = s
				m = i - k + 1
		return m


class Solution:

	def findMaxAverage(self, arr, n, k):
		begin = 0
		if k > n:
			return -1
		sum = 0
		for i in range(0, k, 1):
			sum = sum + arr[i]
		mx = int(sum)
		for i in range(0, n - k, 1):
			sum = sum + arr[i + k] - arr[i]
			if sum >= mx:
				mx = sum
				begin = i + 1
		return begin


class Solution:

	def findMaxAverage(self, arr, n, k):
		currentSum = 0
		index = 0
		for i in range(k):
			currentSum += arr[i]
		maxSum = currentSum
		for i in range(1, n - k + 1):
			currentSum = currentSum + arr[i + k - 1] - arr[i - 1]
			if currentSum > maxSum:
				maxSum = currentSum
				index = i
		return index


class Solution:

	def findMaxAverage(self, arr, n, k):
		ws = 0
		we = 0
		wsum = 0
		result = 0
		max_sum = 0
		for we in range(len(arr)):
			if we >= k:
				wsum += arr[we]
				wsum -= arr[ws]
				ws += 1
				if wsum > max_sum:
					max_sum = wsum
					result = ws
			else:
				wsum += arr[we]
				if we == k - 1:
					max_sum = wsum
		return result


class Solution:

	def findMaxAverage(self, arr, n, k):
		S = sum(arr[:k])
		ans = 0
		we = k - 1
		ws = 0
		temp = S / k
		while we + 1 < n:
			we += 1
			S = S + arr[we] - arr[ws]
			ws += 1
			if temp <= S / k:
				temp = S / k
				ans = ws
		return ans


import math

class Solution:

	def findMaxAverage(self, arr, n, k):
		ws = 0
		maxavg = -math.inf
		wsum = 0
		ans = 0
		for we in range(n):
			wsum += arr[we]
			if we >= k - 1:
				temp = wsum / k
				if temp > maxavg:
					maxavg = temp
					ans = ws
				wsum -= arr[ws]
				ws += 1
		return ans


class Solution:

	def findMaxAverage(self, arr, n, k):
		start = 0
		sum = 0
		m = float('-inf')
		for i in range(n):
			sum += arr[i]
			if i >= k - 1:
				p = sum / k
				if p > m:
					m = p
					a = start
				sum -= arr[start]
				start += 1
		return a


class Solution:

	def findMaxAverage(self, nums, n, k):
		start = 0
		s = 0
		m = float('-inf')
		for i in range(len(nums)):
			s += nums[i]
			if i >= k - 1:
				p = s / 4
				if m < p:
					m = p
					a = start
				s = s - nums[start]
				start += 1
		return a


class Solution:

	def findMaxAverage(self, arr, n, k):
		aux = [0] * n
		for i in range(n):
			aux[i] = aux[i - 1] + arr[i]
		max_sum = aux[k - 1]
		last_index = k - 1
		for i in range(k, n):
			new_sum = aux[i] - aux[i - k]
			if new_sum > max_sum:
				max_sum = new_sum
				last_index = i
		return last_index - k + 1


class Solution:

	def findMaxAverage(self, arr, n, k):
		ans = []
		curr_sum = 0
		for i in arr[:k]:
			curr_sum += i
		ans.append(curr_sum / k)
		for i in range(1, n - k + 1):
			curr_sum = curr_sum - arr[i - 1] + arr[i + k - 1]
			ans.append(curr_sum / k)
		return ans.index(max(ans))


class Solution:

	def findMaxAverage(self, arr, n, k):
		sum1 = sum(arr[0:k])
		max1 = sum1
		count = 0
		for i in range(k, n):
			sum1 = sum1 - arr[i - k] + arr[i]
			if max1 < sum1:
				max1 = sum1
				count = i - k + 1
		return count


class Solution:

	def findMaxAverage(self, arr, n, k):
		if k > n:
			return -1
		sm = sum(arr[:k])
		max_sum = sm
		max_end = k - 1
		for i in range(k, n):
			sm = sm + arr[i] - arr[i - k]
			if sm > max_sum:
				max_sum = sm
				max_end = i
		return max_end - k + 1
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		k = int(input())
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findMaxAverage(arr, n, k)
		for i in range(ans, ans + k):
			print(arr[i], end=' ')
		print()
		tc -= 1


class Solution:

	def findMaxAverage(self, arr, n, k):
		sum = 0
		index = 0
		for i in range(k):
			sum += i
		max = sum
		for j in range(k, n):
			sum = sum + arr[j] - arr[j - k]
			if sum > max:
				max = sum
				index = j - k + 1
		return index
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		k = int(input())
		n = int(input())
		arr = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.findMaxAverage(arr, n, k)
		for i in range(ans, ans + k):
			print(arr[i], end=' ')
		print()
		tc -= 1


class Solution:

	def findMaxAverage(self, nums, n, k):
		maxSum = float('-inf')
		summ = 0
		i = j = 0
		res = -1
		while j < n:
			summ += nums[j]
			if j - i + 1 == k:
				if summ > maxSum:
					maxSum = summ
					res = i
				summ -= nums[i]
				i += 1
			j += 1
		return res


class Solution:

	def findMaxAverage(self, a, n, k):
		idx = 0
		s = sum(a[:k])
		ans = s
		for i in range(k, n):
			s += a[i] - a[i - k]
			if s > ans:
				ans = s
				idx = i - k + 1
		return idx


from itertools import accumulate
import sys

class Solution:

	def findMaxAverage(self, arr, n, k):
		prefSum = [0] + list(accumulate(arr))
		maxSum = -sys.maxsize - 1
		maxArr = None
		for i in range(0, n + 1 - k):
			maxSum = max(maxSum, prefSum[i + k] - prefSum[i])
			if prefSum[i + k] - prefSum[i] == maxSum:
				maxArr = i
		return maxArr


class Solution:

	def findMaxAverage(self, arr, n, k):
		if k > n:
			return -1
		sum1 = arr[0]
		for i in range(1, k):
			sum1 += arr[i]
		max_sum = sum1
		max_end = k - 1
		for i in range(k, n):
			sum1 = sum1 + arr[i] - arr[i - k]
			if sum1 > max_sum:
				max_sum = sum1
				max_end = i
		return max_end - k + 1


class Solution:

	def findMaxAverage(self, arr, n, k):
		sume = sum(arr[:k])
		li = [sume]
		for i in range(1, n - k + 1):
			sume = sume - arr[i - 1] + arr[i + k - 1]
			li.append(sume)
		return li.index(max(li))


class Solution:

	def findMaxAverage(self, arr, n, k):
		sum_till_here = 0
		max_sum = -999
		start = 0
		end = k - 1
		p = 0
		for i in range(0, k):
			sum_till_here += arr[i]
		max_sum = sum_till_here
		for i in range(k, n):
			p += 1
			sum_till_here = sum_till_here - arr[p - 1] + arr[i]
			if sum_till_here > max_sum:
				max_sum = sum_till_here
				start = p
				end = i
		res = []
		return start


import sys

class Solution:

	def findMaxAverage(self, arr, n, k):
		(i, j) = (0, 0)
		s = 0
		maxi = -sys.maxsize
		pos = -1
		while j < n:
			s += arr[j]
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if s > maxi:
					maxi = s
					pos = i
				s -= arr[i]
				i += 1
				j += 1
		return pos


class Solution:

	def findMaxAverage(self, a, n, k):
		s = 0
		for i in range(k):
			s += a[i]
		m = s
		idd = 0
		for i in range(k, n):
			s = s - a[i - k] + a[i]
			if s > m:
				m = s
				idd = i - k + 1
		return idd


class Solution:

	def findMaxAverage(self, arr, n, k):
		p = 0
		l = sum(arr[:k])
		ans = l
		for i in range(n - k):
			l = l - arr[i] + arr[i + k]
			if l > ans:
				p = i + 1
				ans = l
		return p


class Solution:

	def findMaxAverage(self, arr, n, k):
		if k > n:
			return -1
		if k == n:
			return arr
		s = 0
		for i in range(k):
			s += arr[k]
		mx = s
		start = 0
		for i in range(k, n):
			s += arr[i] - arr[i - k]
			if s > mx:
				s = mx
				start = i - k + 1
		return start


class Solution:

	def findMaxAverage(self, arr, n, k):
		temp = 0
		avg = cusum = sum(arr[0:k])
		for i in range(1, n - k + 1):
			cusum += arr[i + k - 1]
			cusum -= arr[i - 1]
			if cusum > avg:
				avg = cusum
				temp = i
		return temp


import collections

class Solution:

	def findMaxAverage(self, arr, n, k):
		lst = collections.deque()
		sum = 0
		ans = []
		for (idx, val) in enumerate(arr):
			lst.append(val)
			sum += val
			if len(lst) == k:
				avg = sum / (k * 1.0)
				if not ans or (ans and ans[0] < avg):
					ans = [avg, idx - k + 1]
				sum -= lst.popleft()
		return ans[1]


class Solution:

	def findMaxAverage(self, arr, n, k):
		cumSum = {}
		s = 0
		for i in range(0, n):
			s += arr[i]
			cumSum[i] = s
		j = 0
		ma = cumSum[k - 1]
		for i in range(1, n - k + 1):
			if cumSum[i + k - 1] - cumSum[i - 1] > ma:
				ma = cumSum[i + k - 1] - cumSum[i - 1]
				j = i
		return j


class Solution:

	def findMaxAverage(self, arr, n, k):
		Sum = 0
		maxSum = -100000000000.0
		i = 0
		j = 0
		pos = -1
		while j < n:
			Sum += arr[j]
			if j - i + 1 == k:
				if Sum > maxSum:
					maxSum = Sum
					pos = i
				Sum -= arr[i]
				i += 1
			j += 1
		return pos


class Solution:

	def findMaxAverage(self, arr, n, k):
		summ = 0
		left = 0
		summ = sum(arr[:k])
		maxSum = summ
		j = k
		while j < n:
			summ = summ + arr[j] - arr[j - k]
			if summ > maxSum:
				maxSum = summ
				left = j - k + 1
			j += 1
		return left


class Solution:

	def findMaxAverage(self, arr, n, k):
		prefix = [0]
		for i in arr:
			prefix.append(prefix[-1] + i)
		i = k + 1
		res = 0
		m = prefix[k]
		while i <= n:
			sm = prefix[i] - prefix[i - k]
			if sm > m:
				m = sm
				res = i - k
			i += 1
		return res


class Solution:

	def findMaxAverage(self, arr, n, k):
		window_start = 0
		window_sum = [0] * (n - k + 1)
		ws = 0
		for window_end in range(0, n):
			ws += arr[window_end]
			if window_end >= k - 1:
				window_sum[window_start] = ws / k
				ws -= arr[window_start]
				window_start = window_start + 1
		if len(window_sum) == 0:
			return 0
		else:
			max_idx = 0
			max_sum = window_sum[0]
			for idx in range(1, len(window_sum)):
				if window_sum[idx] > max_sum:
					max_sum = window_sum[idx]
					max_idx = idx
		return max_idx


class Solution:

	def findMaxAverage(self, arr, n, k):
		maxsum = -10000000
		l1 = 0
		s = sum(arr[:k])
		if s > maxsum:
			maxsum = s
			l1 = k - 1
		j = 0
		for i in range(k, n):
			s += arr[i]
			s -= arr[j]
			j += 1
			if s > maxsum:
				maxsum = s
				l1 = i
		return l1 - k + 1


class Solution:

	def findMaxAverage(self, arr, n, k):
		prevsum = sum(arr[:k])
		maxsum = prevsum
		ind = 0
		for i in range(1, n - k + 1):
			newsum = prevsum - arr[i - 1] + arr[i + k - 1]
			if newsum > maxsum:
				maxsum = newsum
				ind = i
			prevsum = newsum
		return ind


class Solution:

	def findMaxAverage(self, arr, n, k):
		result = {}
		maxi = float('-inf')
		window_start = 0
		window_sum = 0
		for window_end in range(n):
			right_char = arr[window_end]
			window_sum += right_char
			if window_end >= k - 1:
				avg = window_sum / k
				result[window_start] = avg
				maxi = max(maxi, avg)
				window_sum -= arr[window_start]
				window_start += 1
		for i in result:
			if result[i] == maxi:
				return i


class Solution:

	def findMaxAverage(self, arr, n, k):
		start_inx = 0
		start_sum = 0
		for i in range(k):
			start_sum += arr[i]
		max_sum = start_sum
		i = 0
		j = k
		while j < len(arr):
			start_sum = start_sum - arr[i] + arr[j]
			if start_sum > max_sum:
				max_sum = start_sum
				start_inx = i + 1
			i += 1
			j += 1
		return start_inx


class Solution:

	def findMaxAverage(self, arr, n, k):
		s = 0
		for i in range(k):
			s = s + arr[i]
		mxVal = s
		cridx = 0
		for i in range(n - k):
			s = s - arr[i] + arr[k + i]
			if s > mxVal:
				mxVal = s
				cridx = i + 1
		return cridx


class Solution:

	def findMaxAverage(self, arr, n, k):
		i = 0
		j = 0
		sm = 0
		idx = -1
		avg = -1000
		while j < n:
			sm += arr[j]
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if avg < sm / k:
					avg = sm / k
					idx = i
				sm -= arr[i]
				i += 1
				j += 1
		return idx


class Solution:

	def findMaxAverage(self, arr, n, k):
		sm = sum(arr[:k])
		mx = sm
		f = 0
		res = 0
		for i in range(k, n):
			sm += arr[i] - arr[i - k]
			f += 1
			if sm > mx:
				mx = sm
				res = f
		return res


class Solution:

	def findMaxAverage(self, arr, n, k):
		l = 0
		currsum = sum(arr[:k])
		ans = currsum
		out = 0
		for j in range(k, n):
			currsum -= arr[l]
			l += 1
			currsum += arr[j]
			if currsum > ans:
				ans = currsum
				out = l
		return out


class Solution:

	def findMaxAverage(self, arr, n, k):
		st = 0
		avg = 0.0
		s = 0
		ans = []
		for i in range(k):
			s += arr[i]
		avg = s / k
		res = 0
		for j in range(k, n):
			s -= arr[st]
			st += 1
			s += arr[j]
			if avg < s / k:
				res = st
				avg = s / k
		return res


class Solution:

	def findMaxAverage(self, arr, n, k):
		max_s = s = sum(arr[0:k - 1])
		max_i = 0
		for i in range(1, n - k + 1):
			s -= arr[i - 1]
			s += arr[i + k - 1]
			if s > max_s:
				max_s = s
				max_i = i
		return max_i


class Solution:

	def findMaxAverage(self, arr, n, k):
		idx = 0
		maxsum = s = sum(arr[:k])
		for j in range(k, n):
			s += arr[j] - arr[j - k]
			if s > maxsum:
				maxsum = s
				idx = j - k + 1
		return idx


import math

class Solution:

	def findMaxAverage(self, arr, n, k):
		i = j = 0
		_sum = 0
		start = end = 0
		final_sum = -math.inf
		while j < n:
			_sum += arr[j]
			if j - i + 1 < k:
				j += 1
			elif j - i + 1 == k:
				if _sum > final_sum:
					start = i
					end = j
					final_sum = _sum
				_sum -= arr[i]
				i += 1
				j += 1
		return start


class Solution:

	def findMaxAverage(self, arr, n, k):
		start = 0
		totalSum = sum(arr[:k])
		maxSum = totalSum
		for i in range(k, n):
			totalSum = totalSum + arr[i] - arr[i - k]
			if totalSum > maxSum:
				maxSum = totalSum
				start = i - k + 1
		return start


class Solution:

	def findMaxAverage(self, arr, n, k):
		s = 0
		for i in range(k):
			s += arr[i]
		st = 0
		mx_sum = s
		for i in range(k, n):
			s = s - arr[i - k] + arr[i]
			if s > mx_sum:
				st = i - k + 1
				mx_sum = s
		return st


class Solution:

	def findMaxAverage(self, arr, n, k):
		sum = 0
		max = -10000000
		start = 0
		for i in range(k):
			sum += arr[i]
		if sum > max:
			max = sum
			start = 0
		for i in range(k, len(arr)):
			sum += arr[i]
			sum -= arr[i - k]
			if sum > max:
				max = sum
				start = i - k + 1
		return start


class Solution:

	def findMaxAverage(self, arr, n, k):
		ans = 0
		j = 0
		a = -1
		b = -1
		avg = -float('inf')
		for i in range(n):
			ans += arr[i]
			if i >= k - 1:
				if ans / k >= avg:
					avg = ans / k
					a = j
					b = i
				ans -= arr[j]
				j += 1
		return a


class Solution:

	def findMaxAverage(self, arr, n, k):
		maxs = 0
		ind = 0
		sum = 0
		for i in range(k):
			sum += arr[i]
		maxs = sum
		for i in range(k, n):
			sum = sum - arr[i - k] + arr[i]
			if maxs < sum:
				maxs = sum
				ind = i - k + 1
		return ind