For a given sequence of integers $A = \\{a_0, a_1, ..., a_{n-1}\\}$, perform the following operations.

* count($b, e, k$): print the number of the specific values $k$ in $a_b, a_{b+1}, ..., a_{e-1}$.

Constraints

* $1 \leq n \leq 1,000$
* $-1,000,000,000 \leq a_i, k_i \leq 1,000,000,000$
* $1 \leq q \leq 1,000$
* $0 \leq b < e \leq n$

Input

The input is given in the following format.


$n$
$a_0 \; a_1, ..., \; a_{n-1}$
$q$
$b_1 \; e_1 \; k_1$
$b_2 \; e_2 \; k_2$
:
$b_q \; e_q \; k_q$


The number of elements $n$ and each element $a_i$ are given in the first line and the second line respectively. In the third line, the number of queries $q$ is given and the following $q$ lines, $q$ integers $b_i \; b_e \; k_i$ are given as queries.

Output

For each query, print the number of specified values.

Example

Input

9
1 4 1 4 2 1 3 5 6
3
0 9 1
1 6 1
3 7 5


Output

3
2
0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
import sys
n = int(input())
a = list(map(int, input().split()))
q = int(input())
for q in (list(map(int, line.split())) for line in sys.stdin):
	print(a[q[0]:q[1]].count(q[2]))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split())
	cnt = 0
	for i in A[b:e]:
		if i == k:
			cnt += 1
	print(cnt)


n = int(input())
A = input().split()
for _ in range(int(input())):
	(b, e, k) = input().split()
	print(A[int(b):int(e)].count(k))


def main():
	n = int(input())
	A = list(map(int, input().split()))
	q = int(input())
	for _ in range(q):
		(a, b, c) = map(int, input().split())
		res = 0
		for i in range(a, b):
			if A[i] == c:
				res += 1
		print(res)
main()


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(x, y, z) = map(int, input().split())
	if z in a:
		print(a[x:y].count(z))
	else:
		print(0)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, k) = map(int, input().split())
	print(A[b:e].count(k))


def run():
	n = int(input())
	li = [int(x) for x in input().split()]
	assert len(li) == n
	q = int(input())
	for _ in range(q):
		(b, e, k) = [int(x) for x in input().split()]
		print(li[b:e].count(k))
run()


n = int(input())
a = list(map(int, input().split(' ')))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split(' '))
	print(a[b:e].count(k))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split())
	cnt = 0
	cnt += a[b:e].count(k)
	print(cnt)
	cnt = 0


input()
a = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(b, e, k) = list(map(int, input().split()))
	print(a[b:e].count(k))


def main():
	n = input()
	seq = [int(a) for a in input().split(' ')]
	q = int(input())
	for _ in range(q):
		(b, e, k) = map(int, input().split(' '))
		print(seq[b:e].count(k))
main()


n = int(input())
a = list(map(int, input().split()))
for i in range(int(input())):
	l = list(map(int, input().split()))
	print(a[l[0]:l[1]].count(l[2]))


n = int(input())
num = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	query = list(map(int, input().split()))
	start = query[0]
	end = query[1]
	target = query[2]
	print(num[start:end].count(target))


n = int(input())
A = input().split()
for i in range(int(input())):
	(b, e, k) = input().split()
	print(A[int(b):int(e)].count(k))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split())
	count = 0
	for a_i in a[b:e]:
		if a_i == k:
			count += 1
	print(count)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
Q = list()
for i in range(q):
	tmp = list(map(int, input().split()))
	Q.append(tmp)
for query in Q:
	print(A[query[0]:query[1]].count(query[2]))


d = input()
L = [int(x) for x in input().split()]
n = int(input())
for _ in range(n):
	(b, e, k) = [int(x) for x in input().split()]
	print(L[b:e].count(k))


from sys import stdin
n = int(stdin.readline())
l = list(map(int, stdin.readline().split()))
q = int(stdin.readline())
for i in range(q):
	inp_l = list(map(int, stdin.readline().split()))
	ans = l[inp_l[0]:inp_l[1]].count(inp_l[2])
	print(ans)


input()
A = input().split()
q = int(input())
for _ in [0] * q:
	(b, e, k) = input().split()
	print(A[int(b):int(e)].count(k))


n = int(input())
nums = list(map(int, input().split(' ')))
q = int(input())
for i in range(q):
	op = list(map(int, input().split(' ')))
	print(nums[op[0]:op[1]].count(op[2]))


input()
nums = list(map(int, input().split(' ')))
r = input()
for _ in range(int(r)):
	(f, l, v) = list(map(int, input().split(' ')))
	print(nums[f:l].count(v))


num_int = int(input())
numbers = list(map(lambda x: int(x), input().split()))
num_query = int(input())
for _ in range(num_query):
	(begin, end, num) = map(lambda x: int(x), input().split())
	count = 0
	for elem in numbers[begin:end]:
		if elem == num:
			count += 1
	print(count)


def count(b, e, k, ary):
	sum = 0
	for elem in ary[b:e]:
		if elem == k:
			sum += 1
	return sum

def main():
	n = int(input())
	ary = [int(x) for x in input().split(' ')]
	num_q = int(input())
	for i in range(num_q):
		(b, e, k) = [int(x) for x in input().split(' ')]
		print(count(b, e, k, ary))
main()


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split())
	s = a[b:e]
	print(s.count(k))


n = int(input())
A = list(map(int, input().split()))
q = int(input())

def counta(b, e, k):
	B = A[b:e]
	print(B.count(k))
for i in range(q):
	queryi = list(map(int, input().split()))
	counta(queryi[0], queryi[1], queryi[2])


from functools import reduce
from collections import deque
import sys
input = sys.stdin.readline

def main():
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(int(input())):
		(n1, n2, a) = map(int, input().split())
		count = len(list(filter(lambda x: x == a, l[n1:n2])))
		print(count)
main()


n = int(input())
arr = [*map(int, input().split())]
q = int(input())
while q:
	q -= 1
	(l, r, k) = map(int, input().split())
	print(arr[l:r].count(k))


n = int(input())
s = list(map(int, input().split()))
m = int(input())
for i in range(m):
	l = []
	(a, b, c) = map(int, input().split())
	l = s[a:b]
	print(l.count(c))


n = input()
l = list(map(int, input().split()))
n = int(input())
for i in range(n):
	q = list(map(int, input().split()))
	li = l[q[0]:q[1]]
	print(li.count(q[2]))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split())
	count = 0
	for j in range(b, e):
		if a[j] == k:
			count += 1
	print(count)


def get_wall_index(ary, key, side):
	left = 0
	right = len(ary) - 1
	while left <= right:
		mid = (left + right) // 2
		if ary[mid] < key:
			left = mid + 1
		elif key < ary[mid]:
			right = mid - 1
		else:
			return mid + side
	return left

def main():
	input()
	input_data = list(map(int, input().split()))
	hash_list = {}
	for (i, num) in enumerate(input_data):
		if num not in hash_list:
			hash_list[num] = []
		hash_list[num].append(i)
	query_size = int(input())
	for _ in range(query_size):
		(begin, end, index) = map(int, input().split())
		if index in hash_list:
			left_wall = get_wall_index(hash_list[index], begin, 0)
			right_wall = get_wall_index(hash_list[index], end - 1, 1)
			print(right_wall - left_wall)
		else:
			print(0)
main()


n = int(input())
A = [int(x) for x in input().split()]
q = int(input())
for i in range(q):
	(b, e, k) = (int(x) for x in input().split())
	print(A[b:e].count(k))


input()
listnum = list(map(int, input().split()))
for i in range(int(input())):
	eachq = list(map(int, input().split()))
	listq = listnum[eachq[0]:eachq[1]]
	count = 0
	for i in range(len(listq)):
		if listq[i] == eachq[2]:
			count = count + 1
	print(count)


n = int(input())
A = list(map(int, input().split()))
n2 = int(input())
for i in range(n2):
	(b, e, k) = map(int, input().split())
	print(A[b:e].count(k))


N = int(input())
X = list(map(int, input().split()))
q = int(input())
for i in range(q):
	a = input().split()
	j = int(a[0])
	t = int(a[1])
	s = int(a[2])
	count = 0
	for p in X[j:t]:
		if p == s:
			count += 1
	print(count)


n = int(input())
l = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split())
	print(l[b:e].count(k))


readline = open(0).readline
writelines = open(1, 'w').writelines
N = int(readline())
(*A,) = map(int, readline().split())
Q = int(readline())
ans = []
for q in range(Q):
	(b, e, k) = map(int, readline().split())
	ans.append('%d\n' % A[b:e].count(k))
writelines(ans)


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = list(map(int, input().split()))
	print(A[b:e].count(k))


import sys
sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))
for _ in range(int(sys.stdin.readline())):
	(b, e, k) = map(int, sys.stdin.readline().split())
	print(a[b:e].count(k))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split())
	print(a[b:e].count(k))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(a, b, c) = map(int, input().split())
	print(A[a:b].count(c))


n = int(input())
box = list(map(int, input().split()))
q = int(input())
for _ in range(q):
	(a, b, c) = map(int, input().split())
	print(box[a:b].count(c))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = list(map(int, input().split()))
	print(a[b:e].count(k))


def solve():
	from sys import stdin
	f_i = stdin
	n = f_i.readline()
	A = f_i.readline().split()
	q = int(f_i.readline())
	ans = []
	for i in range(q):
		(b, e, k) = f_i.readline().split()
		ans.append(str(A[int(b):int(e)].count(k)))
	print('\n'.join(ans))
solve()


import sys
input()
arr = list(map(int, input().split()))
qn = int(input())
queries = sys.stdin.readlines()
for i in range(qn):
	(b, e, k) = map(int, queries[i].split())
	print(arr[b:e].count(k))


n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
	(b, e, k) = map(int, input().split())
	print(a[b:e].count(k))


n = int(input())
A = list(map(int, input().split()))
q = int(input())
for i in range(q):
	query = list(map(int, input().split()))
	print(A[query[0]:query[1]].count(query[2]))


def resolve():
	input()
	A = [int(i) for i in input().split()]
	Q = int(input())
	for _ in range(Q):
		q = [int(i) for i in input().split()]
		print(A[q[0]:q[1]].count(q[2]))
resolve()


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for i in range(Q):
	(b, e, k) = map(int, input().split())
	print(A[b:e].count(k))


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
	(b, e, k) = map(int, input().split())
	print(A[b:e].count(k))