#1216. [GESP样题 八级] 区间

[GESP样题 八级] 区间

题目描述

小杨有一个长度为 nn 的正整数序列 AA。

小杨有 qq 次询问。第 ii 次(1≤i≤q1\le i\le q)询问时,小杨会给出 li,ri,xil_i,r_i,x_i,请你求出 xix_i 在 Ali,Ali+1,…AriA_{l_i}, A_{l_i+1}, \dots A_{r_i} 中出现的次数。

输入格式

第一行包含一个正整数 TT,表示数据组数。

对于每组数据:第一行包含一个正整数 nn,表示序列 AA 的长度。
第二行包含 nn 个正整数 A1,A2,…,AnA_1,A_2,\dots,A_n,表示序列 AA。
第三行包含一个正整数 qq,表示询问次数。接下来 qq 行,每行三个正整数 li,ri,xil_i,r_i,x_i,表示一组询问。

输出格式

对于每组数据,输出 qq 行。第 ii 行(1≤i≤q1\le i\le q)输出一个非负整数,表示第 ii 次询问的答案。

样例

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

题目来源:洛谷 P10288