问题描述

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

输入格式

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

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

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

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

输出格式

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

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

评测用例规模与约定

对于 $20\%$ 的评测用例, $n, m \leq 500,1 \leq a_1, a_2, \cdots, a_n \leq 1000$;

对于 $40\%$ 的评测用例, $n, m \leq 5000$;

对于所有评测用例, $1 \leq n, m \leq 100000,1 \leq a_1, a_2, \cdots, a_n \leq 100000,1 \leq l_i \leq r_i \leq n, 1 \leq k_i \leq n$。