You are given an array of N elements and num queries, In each query you are given three numbers L,R and K and you have to tell, how many indexes are there in between L and R(L<=i<=R) such that the frequency of a[i] from index i to n-1 is k.
Note: 0-based indexing
Example 1:
Input:
N=5
num=3
A={1,1,3,4,3}
Q={{0,2,2},{0,2,1},{0,4,2}}
Output:
2 1 2
Explanation:
For query 1: 0 2 2
L=0,R=2,K=2
let, L<=i<=R
For i=0: frequency of a[i] i.e. 1 from i to n-1 is 2.
For i=1: frequency of a[i] i.e. 1 from i to n-1 is 1.
For i=2: frequency of a[i] i.e. 3 from i to n-1 is 2.
Hence we have two elements from index 0 to 2 
whose frequency from i to n-1 is 2.
For query 2: 0 2 1
L=0,R=2,K=1
As we can see from the above query that there is 
only a single element in 0 to 2 whose frequency 
from i to n-1 is 1.
For query 3: 0 4 2
The answer will be 2 because of the index 0 and 2.
Example 2:
Input:
N=5
num=2
A={1,1,1,1,1}
Q={{0,4,2},{0,4,1}}
Output:
1 1 
Explanation: 
For query 1: 0 4 2 
L=0,R=4,K=2 
let, L<=i<=R 
For i=0: frequency of a[i] i.e. 1 from i to n-1 is 5. 
For i=1: frequency of a[i] i.e. 1 from i to n-1 is 4. 
For i=2: frequency of a[i] i.e. 1 from i to n-1 is 3.
For i=3: frequency of a[i] i.e. 1 from i to n-1 is 2.
For i=4: frequency of a[i] i.e. 1 from i to n-1 is 1. 
Hence we have one elements from index 0 to 4 whose frequency from i to n-1 is 2. 
Similarly For query 2: 
there is only 1 element in 0 to 4 whose frequency from i to n-1 is 1.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N^{2})
Your Task:
You don't need to read input or print anything. Your task is to complete the function solveQueries() which take two variable N and num representing the length of the original array and number of queries and two arrays as input, A and Q representing the original array and an array of queries(2-D array with 3 columns of L,R and K respectively), and returns the array of length num with the solution to each query.
 
Constraints:
1 <= N <= 10^{3}
0 <= Q < 10^{3}
1 <= A[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Range queries

Starter code: from typing import List







class Solution:

    def solveQueries(self, N : int, num : int, A : List[int], Q : List[List[int]]) -> List[int]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		dp = [[0 for _ in range(N)] for _ in range(N + 1)]
		for i in range(N - 1, -1, -1):
			for j in range(N):
				dp[i][j] = dp[i + 1][j]
				if A[i] == A[j]:
					dp[i][j] += 1
		ret = []
		for (a, b, c) in Q:
			tmp = 0
			for i in range(a, b + 1):
				if dp[i][i] == c:
					tmp += 1
			ret.append(tmp)
		return ret


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		dp = [0] * N
		for i in range(N):
			c = 0
			for j in range(i, N):
				if A[j] == A[i]:
					c += 1
			dp[i] = c
		res = []
		for i in Q:
			c = 0
			for j in range(i[0], i[1] + 1):
				if dp[j] == i[2]:
					c += 1
			res.append(c)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		pre = [[0] * (N + 1) for _ in range(N + 1)]
		for i in range(N):
			cnt = 0
			for j in range(i, N):
				if A[i] == A[j]:
					cnt += 1
			pre[i][cnt] += 1
		for i in range(N):
			for j in range(1, N):
				pre[j][i] += pre[j - 1][i]
		ans = []
		for i in range(num):
			L = Q[i][0]
			R = Q[i][1]
			K = Q[i][2]
			if L == 0:
				ans.append(pre[R][K])
			else:
				ans.append(pre[R][K] - pre[L - 1][K])
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		suffixocc = [0] * N
		suffixmap = dict()
		for i in range(N - 1, -1, -1):
			if A[i] not in suffixmap:
				suffixmap[A[i]] = 1
			else:
				suffixmap[A[i]] += 1
			suffixocc[i] = suffixmap[A[i]]
		arr = [suffixocc[l:r + 1].count(k) for (l, r, k) in Q]
		return arr


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		reusable = dict()
		lastindex = N - 1
		out = [0 for _ in range(len(Q))]
		for q in range(len(Q)):
			if lastindex >= Q[q][0]:
				for i in range(lastindex, Q[q][0] - 1, -1):
					reusable[A[i]] = reusable.get(A[i], 0) + 1
				lastindex = Q[q][1]
			else:
				for i in range(lastindex + 1, Q[q][0]):
					reusable[A[i]] -= 1
				lastindex = Q[q][1]
			for i in range(Q[q][0], Q[q][1] + 1):
				if reusable[A[i]] == Q[q][2]:
					out[q] += 1
				reusable[A[i]] -= 1
		return out


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		ans = [0 for _ in range(num)]
		counts = [1 for _ in range(N)]
		for i in range(N):
			for j in range(i + 1, N):
				if A[j] == A[i]:
					counts[i] += 1
		index = 0
		for (left, right, k) in Q:
			count_nums = 0
			for i in range(left, right + 1):
				if counts[i] == k:
					count_nums += 1
			ans[index] = count_nums
			index += 1
		return ans


from typing import List

class Solution:

	def solveQueries(self, n: int, num: int, a: List[int], Q: List[List[int]]) -> List[int]:
		d = {}
		for i in range(n):
			if a[i] not in d.keys():
				d[a[i]] = 1
			else:
				d[a[i]] += 1
		freq = []
		ans = []
		for i in range(n):
			freq.append(d[a[i]])
			d[a[i]] -= 1
		for i in range(len(Q)):
			cnt = 0
			for j in range(Q[i][0], Q[i][1] + 1):
				if freq[j] == Q[i][2]:
					cnt += 1
			ans.append(cnt)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		freq = {}
		freq_arr = [0] * N
		result = []
		for i in range(N - 1, -1, -1):
			if A[i] in freq:
				freq[A[i]] = freq[A[i]] + 1
			else:
				freq[A[i]] = 1
			freq_arr[i] = freq[A[i]]
		for query in Q:
			count = 0
			for i in range(query[0], query[1] + 1):
				if freq_arr[i] == query[2]:
					count += 1
			result.append(count)
		return result


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		hashMap = {}
		right = [0] * N
		for i in range(N - 1, -1, -1):
			if A[i] in hashMap:
				right[i] += hashMap[A[i]] + 1
				hashMap[A[i]] += 1
			else:
				right[i] = 1
				hashMap[A[i]] = 1
		ans = []
		for i in range(len(Q)):
			l = Q[i][0]
			r = Q[i][1]
			k = Q[i][2]
			count = 0
			for j in range(l, r + 1):
				if right[j] == k:
					count += 1
			ans.append(count)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		d = dict()
		for i in range(N):
			d[i] = A[i:N].count(A[i])
		ans = list()
		c = 0
		for l in Q:
			for i in range(l[0], l[1] + 1):
				if d[i] == l[2]:
					c += 1
			ans.append(c)
			c = 0
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		prefix = [0] * N
		dic = {}
		for i in range(N):
			a = A[i]
			dic[a] = dic.get(a, 0) + 1
			prefix[i] = dic[a]
		ans = []
		for q in Q:
			(l, r, k) = q
			count = 0
			for i in range(l, r + 1):
				freq_L = prefix[i] - 1
				freq_R = dic[A[i]]
				if freq_R - freq_L == k:
					count += 1
			ans.append(count)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		mp = {}
		freq = [0 for i in range(N)]
		res = []
		for i in range(N - 1, -1, -1):
			if A[i] not in mp:
				mp[A[i]] = 1
			else:
				mp[A[i]] += 1
			freq[i] = mp[A[i]]
		for q in Q:
			l = q[0]
			r = q[1]
			k = q[2]
			cnt = 0
			for x in range(l, r + 1):
				if freq[x] == k:
					cnt += 1
			res.append(cnt)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		B = [1] * N
		for i in range(N - 1, -1, -1):
			for j in range(i + 1, N):
				if A[i] == A[j]:
					B[i] = B[j] + 1
					break
		ans = []
		for arr in Q:
			temp = 0
			for i in range(arr[0], arr[1] + 1):
				if B[i] == arr[2]:
					temp += 1
			ans.append(temp)
		return ans


from typing import List
from collections import defaultdict

class Solution:

	def solveQueries(self, n, num, arr, queries):
		ans = []
		d = defaultdict(int)
		lis = [0 for i in range(n + 1)]
		for i in range(n - 1, -1, -1):
			d[arr[i]] += 1
			lis[i] = d[arr[i]]
		for (l, r, k) in queries:
			cnt = 0
			for i in range(l, r + 1):
				if lis[i] == k:
					cnt += 1
			ans.append(cnt)
		return ans


from typing import List
import copy

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		dp = [0 for i in range(N)]
		ans = []
		for i in range(0, N):
			ele = A[i]
			freq_ele = 0
			for j in range(i, N):
				if ele == A[j]:
					freq_ele += 1
			dp[i] = freq_ele
		for i in range(0, num):
			count = 0
			for j in range(Q[i][0], Q[i][1] + 1):
				if Q[i][2] == dp[j]:
					count += 1
			ans.append(count)
		return ans


from typing import List
from bisect import bisect_left, bisect_right
from collections import defaultdict

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		frequencies = defaultdict(int)
		for a in A:
			frequencies[a] += 1
		freq_to_ids = defaultdict(list)
		for (i, a) in enumerate(A):
			freq = frequencies[a]
			freq_to_ids[freq].append(i)
			frequencies[a] -= 1
		ans = []
		for (l, r, k) in Q:
			ids = freq_to_ids[k]
			left_idx = bisect_left(ids, l)
			right_idx = bisect_right(ids, r)
			count = right_idx - left_idx
			ans.append(count)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		count_array = []
		counts = dict()
		for i in range(len(A) - 1, -1, -1):
			if not A[i] in counts:
				counts[A[i]] = 0
			counts[A[i]] += 1
			count_array.insert(0, (A[i], counts[A[i]]))
		ans_array = []
		for q in Q:
			(L, R, K) = q
			ans = 0
			for i in range(L, R + 1):
				if count_array[i][1] == K:
					ans += 1
			ans_array.append(ans)
		return ans_array


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		dp = [[0 for _ in range(N)] for _ in range(N)]
		for i in range(N):
			dp[i][i] = 1
			for j in range(i + 1, N):
				dp[i][j] = dp[i][j - 1]
				if A[j] == A[i]:
					dp[i][j] += 1
		res = []
		for q in Q:
			(L, R, K) = q
			count = 0
			for i in range(L, R + 1):
				if dp[i][N - 1] == K:
					count += 1
			res.append(count)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		occs = [0] * N
		appears = dict()
		for i in range(N - 1, -1, -1):
			occs[i] = appears.get(A[i], 0) + 1
			appears[A[i]] = appears.get(A[i], 0) + 1
		apps = list()
		for query in Q:
			L = query[0]
			R = query[1]
			K = query[2]
			count = 0
			for i in range(L, R + 1):
				if occs[i] == K:
					count += 1
			apps.append(count)
		return apps


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		freq = []
		for i in range(N):
			c = 0
			for j in range(i, N):
				if A[j] == A[i]:
					c += 1
			freq.append(c)
		res = []
		for (l, r, k) in Q:
			c = 0
			for i in range(l, r + 1):
				if freq[i] == k:
					c += 1
			res.append(c)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		res = []
		for q in Q:
			(l, r, k) = list(map(int, q))
			d = {}
			c = 0
			for i in range(l, N):
				if A[i] not in d:
					d[A[i]] = 1
				else:
					d[A[i]] += 1
			for i in range(l, r + 1):
				if d[A[i]] == k:
					c += 1
				d[A[i]] -= 1
			res.append(c)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		l = []
		x1 = []
		i = 0
		for i in range(N):
			x = A[i:N].count(A[i])
			l.append(x)
		for i in range(num):
			p = Q[i][0]
			p1 = Q[i][1]
			p2 = Q[i][2]
			c = 0
			for j in range(p, p1 + 1):
				if l[j] == p2:
					c = c + 1
			x1.append(c)
		return x1


from typing import List

class Solution:

	def solveQueries(self, n: int, num: int, arr: List[int], Q: List[List[int]]) -> List[int]:
		(d, l) = (dict(), [0 for i in range(n)])
		for i in range(n - 1, -1, -1):
			if arr[i] not in d:
				d[arr[i]] = 1
			else:
				d[arr[i]] += 1
			l[i] = d[arr[i]]
		ans = list()
		for i in range(num):
			(left, r, ku) = (Q[i][0], Q[i][1], Q[i][2])
			count = 0
			for j in range(left, r + 1):
				if l[j] == ku:
					count += 1
			ans.append(count)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		ans_list = []
		obj = []
		for a in range(N):
			count = 0
			for b in range(a, N):
				if A[a] == A[b]:
					count = count + 1
			obj.append(count)
		for i in range(num):
			L = Q[i][0]
			R = Q[i][1]
			K = Q[i][2]
			k_count = 0
			for j in range(L, R + 1):
				if obj[j] == K:
					k_count = k_count + 1
			ans_list.append(k_count)
		return ans_list


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		freq = []
		for i in range(N):
			a = A[i]
			count = 0
			for j in range(i, N):
				if A[j] == a:
					count += 1
			freq.append((A[i], count))
		ans = []
		for i in range(num):
			count = 0
			l = Q[i][0]
			r = Q[i][1]
			k = Q[i][2]
			for j in range(l, r + 1):
				if freq[j][1] == k:
					count += 1
			ans.append(count)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, arr: List[int], Q: List[List[int]]) -> List[int]:
		freq = [0] * N
		d = dict()
		for i in range(N - 1, -1, -1):
			d[A[i]] = 1 + d.get(A[i], 0)
			freq[i] = d[A[i]]
		i = 0
		result = []
		while i < num:
			l = Q[i][0]
			r = Q[i][1]
			k = Q[i][2]
			count = 0
			while l <= r:
				if freq[l] == k:
					count += 1
				l += 1
			result.append(count)
			i += 1
		return result


from typing import List
from collections import defaultdict

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		d = defaultdict(int)
		right = []
		for i in range(N - 1, -1, -1):
			d[A[i]] += 1
			right.append(d[A[i]])
		right.reverse()
		ans = []
		for i in range(num):
			count = 0
			for j in range(Q[i][0], Q[i][1] + 1):
				if right[j] == Q[i][2]:
					count += 1
			ans.append(count)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		memDict = {}
		ref = [1 for _ in range(N)]
		for i in reversed(range(N)):
			num = A[i]
			if num not in memDict:
				ref[i] = 1
				memDict[num] = 1
			else:
				ref[i] = memDict[num] + 1
				memDict[num] += 1
		ans = []
		for i in range(len(Q)):
			res = 0
			l = Q[i][0]
			r = Q[i][1]
			k = Q[i][2]
			for j in range(l, r + 1):
				if ref[j] == k:
					res += 1
			ans.append(res)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		temp = [0] * N
		mp = {}
		for i in range(N - 1, -1, -1):
			if A[i] in mp:
				mp[A[i]] += 1
				temp[i] = mp[A[i]]
			else:
				mp[A[i]] = 1
				temp[i] = mp[A[i]]
		res = []
		for i in range(num):
			count = 0
			for j in range(Q[i][0], Q[i][1] + 1):
				if temp[j] == Q[i][2]:
					count += 1
			res.append(count)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		l = [0] * N
		d = dict()
		for i in range(N - 1, -1, -1):
			if A[i] not in d:
				d[A[i]] = 1
			else:
				d[A[i]] += 1
			l[i] = d[A[i]]
		i = 0
		result = []
		while i < num:
			j1 = Q[i][0]
			j2 = Q[i][1]
			j3 = Q[i][2]
			count = 0
			while j1 <= j2:
				if l[j1] == j3:
					count += 1
				j1 += 1
			result.append(count)
			i += 1
		return result


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, arr: List[int], Q: List[List[int]]) -> List[int]:
		ans = []
		freq = [0] * N
		dic = {}
		for i in range(N):
			if arr[i] in dic:
				freq[i] = dic[arr[i]] + 1
				dic[arr[i]] += 1
			else:
				freq[i] = 1
				dic[arr[i]] = 1
		for q in Q:
			l = q[0]
			r = q[1]
			k = q[2]
			cnt = 0
			vis = []
			for i in range(l, r + 1):
				if arr[i] not in vis and dic[arr[i]] - freq[i] + 1 == k:
					cnt += 1
					vis.append(arr[i])
			ans.append(cnt)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		freq_ = []
		for i in range(N):
			c = 0
			for j in range(i, N):
				if A[i] == A[j]:
					c += 1
			freq_.append(c)
		res = []
		for i in range(num):
			L = Q[i][0]
			R = Q[i][1]
			k = Q[i][2]
			s = 0
			for j in range(L, R + 1):
				if freq_[j] == k:
					s += 1
			res.append(s)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		finalans = []
		ans = []
		for i in range(N):
			countt = 0
			for j in range(i, N):
				if A[i] == A[j]:
					countt += 1
			ans.append(countt)
		for query in range(num):
			L = Q[query][0]
			R = Q[query][1]
			k = Q[query][2]
			similar = 0
			for j in range(L, R + 1):
				if ans[j] == k:
					similar += 1
			finalans.append(similar)
		return finalans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		dic = {}
		for i in A:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		res = []
		for i in Q:
			(l, r, k) = (i[0], i[1], i[2])
			newdict = dic.copy()
			count = 0
			for x in range(0, l):
				newdict[A[x]] -= 1
			for x in range(l, r + 1):
				if newdict[A[x]] == k:
					count += 1
				newdict[A[x]] -= 1
			res.append(count)
		return res


from typing import List
from collections import defaultdict

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		m = defaultdict(int)
		lis = [0] * N
		ans = []
		for i in range(N - 1, -1, -1):
			m[A[i]] += 1
			lis[i] = m[A[i]]
		for ele in Q:
			temp = 0
			for i in range(ele[0], ele[1] + 1):
				if lis[i] == ele[2]:
					temp += 1
			ans.append(temp)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		arr = [0] * N
		map_ = {}
		ans = []
		for i in range(N - 1, -1, -1):
			if A[i] in map_:
				map_[A[i]] += 1
			else:
				map_[A[i]] = 1
			arr[i] = map_[A[i]]
		for i in range(num):
			(l, r, k) = (Q[i][0], Q[i][1], Q[i][2])
			count = 0
			for i in range(l, r + 1):
				if arr[i] == k:
					count += 1
			ans.append(count)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		count = [0] * N
		mapp = {}
		ans = []
		for i in range(N - 1, -1, -1):
			if A[i] not in mapp:
				count[i] = 1
				mapp[A[i]] = 1
			else:
				mapp[A[i]] += 1
				count[i] = mapp[A[i]]
		for q in Q:
			l = q[0]
			r = q[1]
			val = q[2]
			Count = 0
			for i in range(l, r + 1):
				if count[i] == val:
					Count += 1
			ans.append(Count)
		return ans


from collections import Counter
from typing import List

class Solution:

	def solveQueries(self, n: int, q: int, nums: List[int], queries: List[List[int]]) -> List[int]:
		res = []
		for (l, r, k) in queries:
			freq = Counter(nums[l:])
			cnt = 0
			for i in range(l, r + 1):
				if freq[nums[i]] == k:
					cnt += 1
				freq[nums[i]] -= 1
			res.append(cnt)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		d = {}
		for i in A:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		res = []
		for i in Q:
			(l, r, k) = (i[0], i[1], i[2])
			temp = d.copy()
			count = 0
			for j in range(0, l):
				temp[A[j]] -= 1
			for j in range(l, r + 1):
				if temp[A[j]] == k:
					count += 1
				temp[A[j]] -= 1
			res.append(count)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		ans = []
		helper = [0] * N
		fre = dict()
		idx = N - 1
		for i in A[::-1]:
			if i in fre:
				fre[i] += 1
			else:
				fre[i] = 1
			helper[idx] = fre.copy()
			idx -= 1
		for (l, r, k) in Q:
			count = 0
			for i in range(l, r + 1):
				if helper[i][A[i]] == k:
					count += 1
			ans.append(count)
		return ans


from typing import List
from typing import List
from collections import defaultdict

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		ans = list()
		pre = [0 for i in range(N)]
		d = defaultdict(int)
		for i in range(N - 1, -1, -1):
			d[A[i]] += 1
			pre[i] = d[A[i]]
		for i in Q:
			(l, r, k) = (i[0], i[1], i[2])
			count = 0
			for i in range(l, r + 1):
				if pre[i] == k:
					count += 1
			ans.append(count)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		a = []
		count = []
		for i in range(len(A)):
			c = 0
			for j in range(i, len(A)):
				if A[i] == A[j]:
					c += 1
			a.append(c)
		for k in range(len(Q)):
			L = Q[k][0]
			R = Q[k][1]
			K = Q[k][2]
			co = 0
			for p in range(L, R + 1):
				if a[p] == K:
					co += 1
			count.append(co)
		return count


from typing import List
from bisect import bisect_left, bisect_right

class Solution:

	def solveQueries(self, N, num, a, Q):
		freq = {}
		for x in a:
			freq[x] = freq.get(x, 0) + 1
		mp = {}
		for i in range(N):
			if freq[a[i]] in mp:
				mp[freq[a[i]]].append(i)
			else:
				mp[freq[a[i]]] = [i]
			freq[a[i]] -= 1
		ans = []
		for x in Q:
			(l, r, k) = (x[0], x[1], x[2])
			v = mp.get(k, [])
			it1 = bisect_left(v, l)
			it2 = bisect_right(v, r)
			ans.append(it2 - it1)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		list1 = []
		freq = []
		for i in range(N):
			count = 1
			for j in range(i + 1, N):
				if A[i] == A[j]:
					count += 1
			freq.append(count)
		for i in range(num):
			sum = 0
			for j in range(Q[i][0], Q[i][1] + 1):
				if freq[j] == Q[i][2]:
					sum += 1
			list1.append(sum)
		return list1


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		freq = {}
		ans = []
		temp = [0] * N
		for i in range(N - 1, -1, -1):
			freq[A[i]] = freq.get(A[i], 0) + 1
			temp[i] = freq.get(A[i])
		for (l, r, k) in Q:
			cnt = 0
			while l <= r:
				if temp[l] == k:
					cnt += 1
				l += 1
			ans.append(cnt)
		return ans


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		(arr, d) = ([0 for i in range(N)], dict())
		for i in range(N - 1, -1, -1):
			d[A[i]] = d.get(A[i], 0) + 1
			arr[i] = d[A[i]]
		final_result = []
		for i in Q:
			ans = 0
			for j in range(i[0], i[1] + 1):
				if arr[j] == i[2]:
					ans += 1
			final_result.append(ans)
		return final_result


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, c: List[int], d: List[List[int]]) -> List[int]:
		d1 = {}
		for i in c:
			if i in d1:
				d1[i] += 1
			else:
				d1[i] = 1
		res = []
		for i in d:
			d2 = d1.copy()
			(j, k, f) = i
			t = 0
			for h in range(j):
				if c[h] in d2:
					d2[c[h]] -= 1
			for h in range(j, k + 1):
				if d2[c[h]] == f:
					t += 1
				d2[c[h]] -= 1
			res.append(t)
		return res


from typing import List

class Solution:

	def solveQueries(self, N: int, num: int, A: List[int], Q: List[List[int]]) -> List[int]:
		dp = [0] * N
		res = []
		for i in range(N):
			for j in range(i, N):
				if A[i] == A[j]:
					dp[i] = dp[i] + 1
		for eachq in Q:
			l = eachq[0]
			r = eachq[1]
			k = eachq[2]
			count = 0
			for i in range(l, r + 1):
				if dp[i] == k:
					count = count + 1
			res.append(count)
		return res