Given an array of n integers and q queries. Write a program to find floor value of mean in range l to r for each query in a new line.
Queries are given by an array queries[] of size 2*q. Here queries[2*i] denote l and queries[2*i+1] denote r for i-th query (0<= i <q).
Example 1:
Input : Arr[] = {1, 2, 3, 4, 5}, Q = 3
queries[] = {0, 2, 1, 3, 0, 4}
Output : 2 3 3
Explanation:
Here we can see that the array of 
integers is [1, 2, 3, 4, 5].
Query 1: L = 0 and R = 2
Sum = 6
Integer Count = 3
So, Mean is 2
Query 2: L = 1 and R = 3
Sum = 9
Integer Count = 3
So, Mean is 3
Query 3: L = 0 and R = 4
Sum = 15
Integer Count = 5
So, the Mean is 3.
So, In the end, the function will 
return the array [2, 3, 3] as an answer.
Example 2:
Input : Arr[] = {6, 7, 8, 10}, Q = 2
queries[] = {0, 3, 1, 2}
Output : 7 7
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function findMean() that takes an array (arr), an array of queries (queries), sizeOfArray (n), sizeOfQueriesArray (2*q) and return the array of size q which has the answer for all the queries. The driver code takes care of the printing.
Expected Time Complexity: O(q + n).
Expected Auxiliary Space: O(n).
Constraints: 
1 ≤ q,n ≤ 2*10^{5}
1 ≤ a[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Range queries

Starter code: #User function Template for python3



class Solution:  

    def findMean(self, arr, queries, n, q): 

        # Complete the function

Solutions:
class Solution:

	def findMean(self, arr, queries, n, q):
		lst = []
		for i in range(1, n):
			arr[i] += arr[i - 1]
		for i in range(0, q, 2):
			if queries[i] == 0:
				lst.append(arr[queries[i + 1]] // (queries[i] + queries[i + 1] + 1))
			else:
				lst.append((arr[queries[i + 1]] - arr[queries[i] - 1]) // (queries[i + 1] - queries[i] + 1))
		return lst


class Solution:

	def findMean(self, arr, queries, n, q):
		res = []
		sm_till = []
		s = 0
		for elem in arr:
			s += elem
			sm_till.append(s)
		for index in range(0, q, 2):
			start = queries[index]
			end = queries[index + 1]
			sm = sm_till[end] if start < 1 else sm_till[end] - sm_till[start - 1]
			mean = sm // (end - start + 1)
			res.append(mean)
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		prefixes = [0]
		summa = 0
		for item in arr:
			summa += item
			prefixes.append(summa)
		output = []
		for i in range(0, q, 2):
			summa = prefixes[queries[i + 1] + 1] - prefixes[queries[i]]
			output.append(summa // (1 + queries[i + 1] - queries[i]))
		return output


class Solution:

	def findMean(self, arr, t, n, q):
		l = []
		s = 0
		d = {}
		for i in range(n):
			s += arr[i]
			d[i] = s
		for i in range(0, q, 2):
			if t[i] > 0:
				p = d[t[i + 1]] - d[t[i] - 1]
			else:
				p = d[t[i + 1]]
			p //= t[i + 1] - t[i] + 1
			l.append(p)
		return l


class Solution:

	def findMean(self, arr, queries, n, q):
		ps = [0]
		tot = 0
		for i in range(n):
			tot += arr[i]
			ps.append(tot)
		ans = []
		for i in range(q // 2):
			l = queries[2 * i]
			r = queries[2 * i + 1]
			current_sum = ps[r + 1] - ps[l]
			current_length = r - l + 1
			ans.append(current_sum // current_length)
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		arr1 = arr
		i = 0
		while i < n:
			if i == 0:
				arr1[i] = arr[i]
			else:
				arr1[i] = arr[i] + arr1[i - 1]
			i += 1
		lst = []
		i = 0
		j = 0
		while i < q // 2:
			start = queries[2 * i]
			end = queries[2 * i + 1]
			if start == 0:
				lst.append(arr1[end] // (end - start + 1))
			else:
				lst.append((arr1[end] - arr1[start - 1]) // (end - start + 1))
			i += 1
		return lst


class Solution:

	def findMean(self, arr, queries, n, q):
		v = []
		p = []
		p.append(arr[0])
		for i in range(1, n):
			p.append(arr[i] + p[i - 1])
		for j in range(0, q, 2):
			l = queries[j]
			r = queries[j + 1]
			c = r - l + 1
			if l == 0:
				v.append(p[r] // c)
			else:
				v.append((p[r] - p[l - 1]) // c)
		return v


import math

class Solution:

	def findMean(self, arr, queries, n, q):
		b = []
		c = []
		b.append(arr[0])
		for i in range(1, n):
			b.append(arr[i] + b[i - 1])
		for i in range(0, q, 2):
			x = queries[i]
			y = queries[i + 1]
			z = y - x + 1
			if x == 0:
				c.append(math.floor(b[y] / z))
			else:
				c.append(math.floor((b[y] - b[x - 1]) / z))
		return c


class Solution:

	def findMean(self, arr, queries, n, q):
		ans = []
		for i in range(1, n):
			arr[i] += arr[i - 1]
		for i in range(0, q - 1, 2):
			if queries[i] == 0:
				s = arr[queries[i + 1]]
			else:
				s = abs(arr[queries[i + 1]] - arr[queries[i] - 1])
			m = queries[i + 1] - queries[i] + 1
			ans.append(s // m)
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		c = []
		cnt = 0
		b = [0] * n
		b[0] = arr[0]
		for i in range(1, n):
			b[i] = arr[i] + b[i - 1]
		for j in range(0, len(queries), 2):
			l = queries[j]
			r = queries[j + 1]
			cnt = r - l + 1
			if l == 0:
				s = b[r]
				v = s // cnt
				c.append(v)
			else:
				s = b[r] - b[l - 1]
				v = s // cnt
				c.append(v)
		return c


class Solution:

	def findMean(self, arr, queries, n, q):
		pf_sum = [0 for i in range(n + 2)]
		res = []
		for i in range(0, n):
			pf_sum[i + 1] = pf_sum[i] + arr[i]
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			res.append((pf_sum[r + 1] - pf_sum[l]) // len(range(l, r + 1)))
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		p = [0] * n
		p[0] = arr[0]
		b = []
		for i in range(1, n):
			p[i] = p[i - 1] + arr[i]
		for j in range(0, len(queries), 2):
			l = queries[j]
			r = queries[j + 1]
			if l == 0:
				s = p[r]
				num = r - l + 1
			else:
				s = p[r] - p[l - 1]
				num = r - l + 1
			m = s // num
			b.append(m)
		return b


class Solution:

	def findMean(self, arr, qu, n, q):
		l = [0] * n
		l[0] = arr[0]
		r = []
		for i in range(1, n):
			l[i] = l[i - 1] + arr[i]
		for i in range(0, q, 2):
			p = i
			q = i + 1
			if qu[p] == 0:
				r.append(l[qu[q]] // (qu[q] - qu[p] + 1))
			else:
				r.append((l[qu[q]] - l[qu[p] - 1]) // (qu[q] - qu[p] + 1))
		return r


class Solution:

	def findMean(self, arr, q, n, q1):
		l = []
		l1 = []
		s = 0
		for i in arr:
			s = s + i
			l.append(s)
		t = 0
		w = 0
		for i in range(0, q1, 2):
			if q[i] != 0:
				t = l[q[i + 1]] - l[q[i] - 1]
				s1 = q[i]
				u = q[i + 1]
				w = u - s1 + 1
				f = t // w
				l1.append(f)
			else:
				t = l[q[i + 1]]
				s1 = q[i]
				u = q[i + 1]
				w = u - s1 + 1
				f = t // w
				l1.append(f)
		return l1


class Solution:

	def findMean(self, arr, queries, n, q):
		presum = [0] * n
		ans = []
		suma = 0
		for i in range(n):
			suma += arr[i]
			presum[i] = suma
		for i in range(0, len(queries) - 1, 2):
			izq = queries[i]
			der = queries[i + 1]
			acum = 0
			size = 0
			if izq - 1 >= 0:
				acum = presum[der] - presum[izq - 1]
				size = der - izq + 1
			else:
				acum = presum[der]
				size = der + 1
			ans.append(acum // size)
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		for i in range(1, n):
			arr[i] += arr[i - 1]
		res = []
		for i in range(0, q, 2):
			(l, r) = (queries[i], queries[i + 1])
			temp = arr[r] if l == 0 else arr[r] - arr[l - 1]
			res.append(temp // (r - l + 1))
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		res = []
		for i in range(1, n):
			arr[i] = arr[i] + arr[i - 1]
		for i in range(0, q, 2):
			s = queries[i]
			e = queries[i + 1]
			res.append(arr[e] // (e + 1) if s == 0 else (arr[e] - arr[s - 1]) // (e - s + 1))
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		prefixsum = []
		cur = 0
		for i in range(n):
			cur += arr[i]
			prefixsum.append(cur)
		res = []
		for i in range(0, q, 2):
			s = prefixsum[queries[i + 1]] - prefixsum[queries[i]] + arr[queries[i]]
			d = queries[i + 1] - queries[i] + 1
			res.append(s // d)
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		presum = [x for x in range(n + 1)]
		result = []
		presum[0] = arr[0]
		for i in range(1, n):
			presum[i] = presum[i - 1] + arr[i]
		for i in range(0, len(queries), 2):
			sun = 0
			l = queries[i]
			r = queries[i + 1]
			if l == 0:
				sum = presum[r]
			else:
				sum = presum[r] - presum[l - 1]
			mean = sum // (r - l + 1)
			result.append(mean)
		return result


class Solution:

	def findMean(self, arr, queries, n, q):
		ans = []
		prefix = [0] * n
		prefix[0] = arr[0]
		for i in range(1, n):
			prefix[i] += arr[i] + prefix[i - 1]
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			(val1, val2) = (0, 0)
			if l > 0:
				val1 = prefix[l - 1]
			if r < n:
				val2 = prefix[r]
			ans.append((val2 - val1) // (r - l + 1))
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		pre = [0] * (n + 1)
		pre[0] = arr[0]
		for i in range(1, n):
			pre[i] = pre[i - 1] + arr[i]
		v = list()
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			x = 0
			if l == 0:
				x = pre[r] // (r - l + 1)
			else:
				x = (pre[r] - pre[l - 1]) // (r - l + 1)
			v.append(x)
		return v


class Solution:

	def findMean(self, arr, qu, n, q):
		k = []
		pre = [0] * n
		pre[0] = arr[0]
		for i in range(1, n):
			pre[i] = pre[i - 1] + arr[i]
		for i in range(0, len(qu), 2):
			if qu[i] == 0:
				s = pre[qu[i + 1]] // (qu[i + 1] + 1)
				k.append(s)
			else:
				s = (pre[qu[i + 1]] - pre[qu[i] - 1]) // (qu[i + 1] - qu[i] + 1)
				k.append(s)
		return k


class Solution:

	def findMean(self, arr, queries, n, q):
		d = {}
		c = 0
		for i in range(n):
			c += arr[i]
			d[i] = c
		ans = []
		for i in range(0, len(queries), 2):
			l = queries[i]
			r = queries[i + 1]
			if l == 0:
				ans.append(d[r] // (r + 1))
			else:
				e = d[r] - d[l - 1]
				ans.append(e // (r + 1 - l))
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		for i in range(1, n):
			arr[i] += arr[i - 1]
		a = []
		l = 0
		r = 1
		for i in range(0, q, 2):
			s = 0
			l = queries[i]
			r = queries[i + 1]
			if l == 0:
				s = arr[r]
			else:
				s = arr[r] - arr[l - 1]
			a.append(s // (r - l + 1))
		return a


class Solution:

	def findMean(self, arr, queries, n, q):
		prefix_sum = [0] * len(arr)
		prefix_sum[0] = arr[0]
		for i in range(1, len(arr)):
			prefix_sum[i] = prefix_sum[i - 1] + arr[i]
		result = []
		for i in range(0, len(queries), 2):
			left = queries[i]
			right = queries[i + 1]
			summation = 0
			integer_count = 0
			average = 0
			if left == 0:
				summation = prefix_sum[right]
				integer_count = right - left + 1
				average = int(summation / integer_count)
			else:
				summation = prefix_sum[right] - prefix_sum[left - 1]
				integer_count = right - left + 1
				average = int(summation / integer_count)
			result.append(average)
		return result


class Solution:

	def findMean(self, arr, queries, n, q):
		res = []
		q_sum = [0] * (n + 2)
		for x in range(n):
			q_sum[x + 1] = q_sum[x] + arr[x]
		for x in range(0, q, 2):
			start = queries[x]
			end = queries[x + 1]
			if end == 0:
				res.append(arr[0])
				continue
			res.append((q_sum[end + 1] - q_sum[start]) // (end - start + 1))
		return res


class Solution:

	def findMean(self, arr, qu, n, q):
		s = 0
		b = []
		for i in arr:
			s += i
			b.append(s)
		g = []
		i = 0
		while i + 1 < q:
			l = qu[i]
			r = qu[i + 1]
			h = b[r] - b[l] + arr[l]
			g.append(h // (r - l + 1))
			i += 2
		return g


class Solution:

	def findMean(self, arr, queries, n, q):
		pref_arr = []
		s = 0
		x = 0
		pref_arr.append(0)
		for i in arr:
			s += i
			pref_arr.append(s)
		ans = []
		for i in range(1, len(queries), 2):
			ans.append((pref_arr[queries[i] + 1] - pref_arr[queries[i - 1]]) // (queries[i] - queries[i - 1] + 1))
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		for i in range(1, n):
			arr[i] += arr[i - 1]
		arr.insert(0, 0)
		ans = []
		for i in range(0, q, 2):
			l = queries[i] + 1
			r = queries[i + 1] + 1
			div = r - l + 1
			if div == 0:
				ans.append(0)
			else:
				mean = (arr[r] - arr[l - 1]) // div
				ans.append(mean)
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		res = []
		pre_sum = [0] * n
		pre_sum[0] = arr[0]
		for i in range(1, n):
			pre_sum[i] = pre_sum[i - 1] + arr[i]
		t = len(queries)
		for i in range(0, t, 2):
			L = queries[i]
			R = queries[i + 1]
			if L == 0:
				Sum = pre_sum[R]
			else:
				Sum = pre_sum[R] - pre_sum[L - 1]
			count = R - L + 1
			res.append(Sum // count)
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		ans = []
		for i in range(1, n):
			arr[i] = arr[i] + arr[i - 1]
		num = len(queries) // 2
		x = 0
		y = 1
		for i in range(num):
			if queries[x] == 0:
				xsum = arr[queries[y]]
				y += 2
				x += 2
			else:
				xsum = arr[queries[y]] - arr[queries[x] - 1]
				x += 2
				y += 2
			meani = abs(queries[i + i] - queries[i + i + 1]) + 1
			ans.append(xsum // meani)
		return ans


import math

class Solution:

	def findMean(self, arr, queries, n, q):
		prefix = [arr[0]]
		for i in arr[1:]:
			prefix.append(prefix[-1] + i)
		ans = []
		for (i, j) in zip(range(0, len(queries), 2), range(1, len(queries), 2)):
			s = prefix[queries[j]] - prefix[queries[i]] + arr[queries[i]]
			c = queries[j] - queries[i] + 1
			ans.append(math.floor(s / c))
		return ans


class Solution:

	def findMean(self, arr, query, n, q):
		curr_sum = 0
		mean = []
		for i in range(0, n):
			curr_sum += arr[i]
			arr[i] = curr_sum
		l = 0
		r = 1
		for j in range(q // 2):
			if query[l] == 0:
				range_sum = arr[query[r]]
				integer_count = query[r] + 1
				mean.append(range_sum // integer_count)
			else:
				range_sum = arr[query[r]] - arr[query[l] - 1]
				integer_count = query[r] - query[l] + 1
				mean.append(range_sum // integer_count)
			l += 2
			r += 2
		return mean


class Solution:

	def findMean(self, arr, queries, n, q):
		ans = []
		prefix = [0] * n
		prefix[0] = arr[0]
		for i in range(1, n):
			prefix[i] = prefix[i - 1] + arr[i]
		for i in range(0, q - 1, 2):
			l = queries[i]
			r = queries[i + 1]
			if l == 0:
				c = r + 1
				ans.append(prefix[r] // (r + 1))
			else:
				c = r - l + 1
				z = prefix[r] - prefix[l - 1]
				ans.append(z // c)
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		arr2 = []
		for i in range(n):
			try:
				arr2.append(arr2[-1] + arr[i])
			except IndexError:
				arr2.append(arr[i])
		ans = []
		for i in range(q // 2):
			(L, R) = (queries[i * 2], queries[i * 2 + 1])
			ans.append((arr2[R] - arr2[L] + arr[L]) // (R - L + 1))
		return ans


class Solution:

	def findMean(self, a, que, n, q):
		ans = []
		for i in range(1, n):
			a[i] += a[i - 1]
		l = 0
		r = 1
		while l < q - 1 and r < q:
			if que[l] == 0:
				ans.append(a[que[r]] // (que[r] - que[l] + 1))
			else:
				ans.append((a[que[r]] - a[que[l] - 1]) // (que[r] - que[l] + 1))
			l += 2
			r += 2
		return ans


from math import *

class Solution:

	def findMean(self, arr, queries, n, q):
		ans = []
		for i in range(1, n):
			arr[i] = arr[i] + arr[i - 1]
		for i in range(0, q, +2):
			first = queries[i]
			second = queries[i + 1]
			if first == 0:
				Sum = arr[second]
			else:
				Sum = arr[second] - arr[first - 1]
			diff = second - first + 1
			ans.append(floor(Sum / diff))
		return ans
for _ in range(0, int(input())):
	(n, q) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	queries = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.findMean(arr, queries, n, 2 * q)
	print(*v)


class Solution:

	def findMean(self, arr, queries, n, q):
		pf_sum = [0 for i in range(n + 2)]
		res = []
		for i in range(0, n):
			pf_sum[i + 1] = pf_sum[i] + arr[i]
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			res.append((pf_sum[r + 1] - pf_sum[l]) // len(range(l, r + 1)))
		return res
for _ in range(0, int(input())):
	(n, q) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	queries = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.findMean(arr, queries, n, 2 * q)
	print(*v)


class Solution:

	def findMean(self, a, b, n, q):
		c = [0]
		e = 0
		for i in range(n):
			e += a[i]
			c.append(e)
		ans = []
		for i in range(0, q, 2):
			l = b[i]
			r = b[i + 1]
			ele = (c[r + 1] - c[l]) // (r - l + 1)
			ans.append(ele)
		return ans
for _ in range(0, int(input())):
	(n, q) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	queries = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.findMean(arr, queries, n, 2 * q)
	print(*v)


import math

class Solution:

	def findMean(self, arr, queries, n, q):
		res = []
		prefixarr = [0] * n
		prefixarr[0] = arr[0]
		for i in range(1, n):
			prefixarr[i] = prefixarr[i - 1] + arr[i]
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			if l == 0:
				sm = prefixarr[r]
			else:
				sm = prefixarr[r] - prefixarr[l - 1]
			sl = r - l + 1
			res.append(math.floor(sm / sl))
		return res
for _ in range(0, int(input())):
	(n, q) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	queries = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.findMean(arr, queries, n, 2 * q)
	print(*v)


class Solution:

	def findMean(self, arr, queries, n, q):
		pre = [0] * n
		pre[0] = arr[0]
		for i in range(1, n):
			pre[i] = pre[i - 1] + arr[i]
		res = []
		for i in range(0, q, 2):
			if queries[i] == 0:
				res.append(pre[queries[i + 1]] // (queries[i + 1] + 1))
			else:
				res.append((pre[queries[i + 1]] - pre[queries[i] - 1]) // (queries[i + 1] - queries[i] + 1))
		return res
for _ in range(0, int(input())):
	(n, q) = map(int, input().strip().split())
	arr = list(map(int, input().strip().split()))
	queries = list(map(int, input().strip().split()))
	ob = Solution()
	v = ob.findMean(arr, queries, n, 2 * q)
	print(*v)


class Solution:

	def findMean(self, arr, queries, n, q):
		sumi = 0
		ind = 0
		ind1 = 1
		ans = []
		for i in range(len(arr)):
			sumi += arr[i]
			arr[i] = sumi
		for i in range(int(len(queries) / 2)):
			if queries[ind] == 0:
				ans.append(int(arr[queries[ind1]] / (queries[ind1] + 1)))
			else:
				ans.append(int((arr[queries[ind1]] - arr[queries[ind] - 1]) / (queries[ind1] - queries[ind] + 1)))
			ind += 2
			ind1 += 2
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		p = [arr[0]]
		ans = []
		for i in range(1, n):
			p.append(p[-1] + arr[i])
		for i in range(0, q, 2):
			if queries[i] > 0:
				ans.append(int((p[queries[i + 1]] - p[queries[i] - 1]) / (queries[i + 1] - queries[i] + 1)))
				continue
			ans.append(int(p[queries[i + 1]] / (queries[i + 1] + 1)))
		return ans


import math

class Solution:

	def findMean(self, arr, queries, n, q):
		for i in range(1, n):
			arr[i] += arr[i - 1]
		i = 0
		l1 = []
		while i < q:
			sum1 = 0
			L = queries[i]
			R = queries[i + 1]
			if L == 0:
				sum1 = arr[R]
			else:
				sum1 = arr[R] - arr[L - 1]
			var = sum1 / (R - L + 1)
			var2 = math.floor(var)
			l1.append(var2)
			i += 2
		return l1


class Solution:

	def findMean(self, arr, queries, n, q):
		sum = 0
		prefixsum = []
		for i in arr:
			sum += i
			prefixsum.append(sum)
		res = []
		for i in range(0, len(queries) - 1, 2):
			x1 = queries[i]
			x2 = queries[i + 1]
			count = abs(x2 - x1) + 1
			if x1 >= 1:
				means = int((prefixsum[x2] - prefixsum[x1 - 1]) / count)
				res.append(means)
			else:
				means = int(prefixsum[x2] / count)
				res.append(means)
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		ans = [0] * int(q / 2)
		pf = [0] * n
		pf[0] = arr[0]
		for i in range(1, n):
			pf[i] = arr[i] + pf[i - 1]
		for j in range(0, len(queries), 2):
			sum = 0
			b = int(j / 2)
			d = queries[j]
			e = queries[j + 1]
			if d - 1 >= 0:
				l = pf[d - 1]
			else:
				l = 0
			r = pf[e]
			sum = r - l
			ans[b] = int(sum / (e - d + 1))
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		pre_sum = [arr[0]]
		queries = list(queries)
		final = []
		for i in range(1, len(arr)):
			pre_sum.append(pre_sum[i - 1] + arr[i])
		(i, j) = (0, 1)
		q = len(queries) // 2
		while q > 0:
			x = queries[i]
			y = queries[j]
			if x == 0:
				final.append(pre_sum[y] // (y - x + 1))
			else:
				final.append((pre_sum[y] - pre_sum[x - 1]) // (y - x + 1))
			i = i + 2
			j = j + 2
			q = q - 1
		return final


import math

class Solution:

	def findMean(self, arr, queries, n, q):
		ps = [0] * (n + 2)
		for i in range(n):
			ps[i + 1] = ps[i] + arr[i]
		res = []
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			res.append((ps[r + 1] - ps[l]) // (r - l + 1))
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		prefix_sum = [arr[0]]
		for i in range(1, n):
			prefix_sum.append(prefix_sum[i - 1] + arr[i])
		results = []
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			if l == 0:
				sum_ = prefix_sum[r]
			else:
				sum_ = prefix_sum[r] - prefix_sum[l - 1]
			mean = int(sum_ / (r - l + 1))
			results.append(mean)
		return results


from itertools import accumulate

class Solution:

	def findMean(self, arr, quer, n, q):
		(pre, ret) = ([0] + list(accumulate(arr)), [])
		return ((pre[quer[i + 1] + 1] - pre[quer[i]]) // (quer[i + 1] - quer[i] + 1) for i in range(0, len(quer) - 1, 2))


from math import floor

class Solution:

	def findMean(self, arr, queries, n, q):
		sum1 = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			sum1[i] = sum1[i - 1] + arr[i - 1]
		ans = []
		for j in range(0, len(queries), 2):
			p = queries[j]
			q = queries[j + 1]
			ans.append(floor((sum1[q + 1] - sum1[p]) // (q - p + 1)))
		return ans


import math

class Solution:

	def findMean(self, arr, queries, n, q):
		for i in range(1, n):
			arr[i] += arr[i - 1]
		res = []
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			if l == 0:
				res += [arr[r] // (r + 1)]
			else:
				res += [(arr[r] - arr[l - 1]) // (r - l + 1)]
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		l = []
		l.append(arr[0])
		s = arr[0]
		ans1 = []
		for i in range(1, n):
			s = s + arr[i]
			l.append(s)
		for i in range(0, len(queries), 2):
			(l1, r) = (queries[i], queries[i + 1])
			if l1 == 0:
				ans = l[r] // (r + 1)
			else:
				ans = (l[r] - l[l1 - 1]) // (r - l1 + 1)
			ans1.append(ans)
		return ans1


class Solution:

	def findMean(self, arr, queries, n, q):
		p = [0]
		for num in arr:
			p.append(p[-1] + num)
		p.pop(0)
		ans = []
		for i in range(1, q, 2):
			(left, right) = (queries[i - 1], queries[i])
			if left == 0:
				Sum = p[right]
			else:
				Sum = p[right] - p[left - 1]
			ans.append(Sum // (right - left + 1))
		return ans


class Solution:

	def findMean(self, arr, queries, n, q):
		arraysum = []
		mysum = 0
		for i in range(0, n):
			mysum += arr[i]
			arraysum.append(mysum)
		finalAnswer = []
		for i in range(0, len(queries), 2):
			low = queries[i]
			high = queries[i + 1]
			finalAnswer.append((arraysum[high] - arraysum[low] + arr[low]) // (high - low + 1))
		return finalAnswer


class Solution:

	def findMean(self, arr, queries, n, q):
		for i in range(1, n):
			arr[i] += arr[i - 1]
		res = []
		for i in range(0, q, 2):
			a = queries[i]
			b = queries[i + 1]
			if a == 0:
				res += [arr[b] // (b + 1)]
			else:
				res += [(arr[b] - arr[a - 1]) // (b - a + 1)]
		return res


import math

class Solution:

	def findMean(self, arr, queries, n, q):
		prefix_sum = []
		for i in range(n):
			if i == 0:
				prefix_sum.append(arr[i])
			else:
				prefix_sum.append(prefix_sum[-1] + arr[i])
		output = []
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			mean = prefix_sum[r]
			if l != 0:
				mean -= prefix_sum[l - 1]
			mean = mean / (r - l + 1)
			output.append(math.floor(mean))
		return output


import math

class Solution:

	def findMean(self, arr, queries, n, q):
		prefsum = [0] * n
		s = 0
		p = 0
		for i in arr:
			s += i
			prefsum[p] = s
			p += 1
		res = [0] * (q // 2)
		r = 0
		for i in range(0, q, 2):
			x = prefsum[queries[i + 1]] - prefsum[queries[i]]
			x = x + arr[queries[i]]
			y = queries[i + 1] - queries[i] + 1
			res[r] = math.floor(x / y)
			r += 1
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		temp = []
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
		for i in range(0, len(queries), 2):
			if queries[i] == 0:
				temp.append(int(arr[queries[i + 1]] / (queries[i + 1] - queries[i] + 1)))
			else:
				a = arr[queries[i + 1]] - arr[queries[i] - 1]
				temp.append(int(a / (queries[i + 1] - queries[i] + 1)))
		return temp


class Solution:

	def findMean(self, arr, queries, n, q):
		ans = []
		sol = []
		sum1 = 0
		count = 0
		for j in range(0, n + 2):
			ans.append(0)
		for j in range(0, n):
			ans[j + 1] = ans[j] + arr[j]
		for j in range(0, q, 2):
			l = queries[j]
			r = queries[j + 1]
			sum1 = ans[r + 1] - ans[l]
			count = r - l + 1
			sol.append(int(sum1 / count))
		return sol


class Solution:

	def findMean(self, arr, queries, n, q):
		for i in range(1, n):
			arr[i] = arr[i] + arr[i - 1]
		i = 0
		lst = []
		while i < len(queries):
			start = queries[i]
			end = queries[i + 1]
			if start == 0:
				ans = arr[end] // (end - start + 1)
			else:
				s = arr[start] - arr[start - 1]
				e = arr[end] - arr[start - 1]
				ans = e // (end - start + 1)
			lst.append(ans)
			i = i + 2
		return lst


class Solution:

	def findMean(self, arr, queries, n, q):
		arr2 = []
		p_sum = [0 for i in range(n + 2)]
		for i in range(n):
			p_sum[i + 1] = p_sum[i] + arr[i]
		for i in range(0, q, 2):
			l = queries[i]
			r = queries[i + 1]
			arr2.append((p_sum[r + 1] - p_sum[l]) // (r - l + 1))
		return arr2


class Solution:

	def findMean(self, arr, queries, n, q):
		l = [0] * (n + 2)
		l[0] = arr[0]
		r = []
		for i in range(0, n):
			l[i + 1] = l[i] + arr[i]
		for i in range(0, len(queries), 2):
			a = queries[i]
			b = queries[i + 1]
			k = l[b + 1] - l[a]
			r.append(k // len(range(a, b + 1)))
		return r


class Solution:

	def findMean(self, arr, queries, n, q):
		sums = [0]
		res = []
		for (i, a) in enumerate(arr):
			sums.append(sums[-1] + a)
		for query in range(int(q / 2)):
			s = queries[query * 2]
			e = queries[query * 2 + 1]
			q_sum = sums[e + 1] - sums[s]
			res.append(int(q_sum / (e - s + 1)))
		return res


class Solution:

	def findMean(self, arr, queries, n, q):
		ans = []
		for i in range(1, n):
			arr[i] = arr[i] + arr[i - 1]
		for i in range(0, q, 2):
			arr_start = queries[i]
			arr_end = queries[i + 1]
			if queries[i] == 0:
				start = 0
			else:
				start = arr[arr_start - 1]
			end = arr[arr_end]
			ans.append(int((end - start) / (arr_end - arr_start + 1)))
		return ans