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

第二行包含 n 个整数 a₁, a₂, · · · , a_n，表示数列中的数。

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

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

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 ≤ 500, 1 ≤ a₁, a₂, · · · , a_n ≤ 1000；

对于 40% 的评测用例，n, m ≤ 5000；

对于所有评测用例，1 ≤ n, m ≤ 100000, 1 ≤ a₁, a₂, · · · , a_n ≤ 100000, 1 ≤ l_i ≤ r_i ≤ n, 1 ≤ k_i ≤ n。