给定一个数列 $A = (a_1, a_2, · · · , a_n)$，给出若干询问，每次询问某个区间 $[l_i,r_i]$ 内恰好出现 $k_i$ 次的数有多少个。

输入格式

输入第一行包含一个整数 $n$ 表示数列长度。

第二行包含 $n$ 个整数 $a_1, a_2, · · · , a_n$，表示数列中的数。

第三行包含一个整数 $m$ 表示询问次数。

接下来 $m$ 行描述询问，其中第 $i$ 行包含三个整数 $l_i,r_i,k_i$ 表示询问 $[l_i,r_i]$ 区间内有多少数出现了 $k_i$ 次。

输出格式

输出 $m$ 行，分别对应每个询问的答案。

数据范围

对于 $20\%$ 的评测用例，$n, m ≤ 500$，$1 ≤ a_1, a_2, · · · , a_n ≤ 1000$；
对于 $40\%$ 的评测用例，$n, m ≤ 5000$；
对于所有评测用例，$1 ≤ n, m ≤ 100000$，$1 ≤ a_1, a_2, · · · , a_n ≤ 100000$，$1 ≤ l_i ≤ r_i ≤ n$，$1 ≤ k_i ≤ n$。

输入样例：

3
1 2 2
5
1 1 1
1 1 2
1 2 1
1 2 2
1 3 2

输出样例：

1
0
2
0
1