背景

GESP八级样题

描述

小杨有一个长度为 $n$ 的正整数序列 $A$ 。 小杨有 $q$ 次询问。第 $i$ 次（$1 ≤ i ≤ q$）询问时，小杨会给出 $l_i, r_i, x_i$ ，请你求出 $x_i$ 在 $A_{l_i}, A_{l_i+1}, ... A_{r_i}$中出现的次数。

格式

输入

第一行包含一个正整数 $T$ ，表示数据组数。

对于每组数据：第一行包含一个正整数 $n$，表示序列 $A$ 的长度。第二行包含 $n$ 个正整数 $A_1, A_2, ... , A_n$，表示序列 $A$。第三行包含一个正整数 $q$，表示询问次数。接下来 $q$ 行，每行三个正整数 $l_i, r_i, x_i$ ，表示一组询问。

输出

对于每组数据，输出 $q$ 行。第 $i$行（$1 ≤ i ≤ q$ ）输出一个非负整数，表示第 $i$ 次询问的答案。

样例

2 
5 
7 4 6 1 1 
2 
1 2 3 
1 5 1 
5 
1 2 3 4 5 
2 
5 5 3 
1 4 3

0
2
0
1

子任务

对于全部数据，保证有$ 1 ≤ T ≤ 5， 1 ≤ n ≤ 10^5， 1 ≤ q ≤ 10^5， 1 ≤ A_i ≤ 10^9$。

限制

时间限制：1.0s 内存限制：128.0MB