Background

Related multiple-choice and true/false problems: https://ti.luogu.com.cn/problemset/1108.

Problem Description

Xiao Yang has a positive integer sequence $A$ of length $n$.

Xiao Yang has $q$ queries. In the $i$-th query ($1 \le i \le q$), Xiao Yang gives $l_i, r_i, x_i$. Please find how many times $x_i$ appears in $A_{l_i}, A_{l_i+1}, \dots, A_{r_i}$.

Input Format

The first line contains a positive integer $T$, indicating the number of test cases.

For each test case: the first line contains a positive integer $n$, indicating the length of sequence $A$.
The second line contains $n$ positive integers $A_1, A_2, \dots, A_n$, representing the sequence $A$.
The third line contains a positive integer $q$, indicating the number of queries. The next $q$ lines each contain three positive integers $l_i, r_i, x_i$, representing one query.

Output Format

For each test case, output $q$ lines. On the $i$-th line ($1 \le i \le q$), output a non-negative integer representing the answer to the $i$-th query.

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

Hint

Constraints

For all testdata, it is guaranteed that $1 \le T \le 5$, $1 \le n, q \le 10^5$, and $1 \le A_i \le 10^9$.

Translated by ChatGPT 5