题目描述

给定一个数列A = (a1, a2, ... , an)，给出若干询问。 每次询问某个区间[l, r]内恰好出现k次的数有多少个。

输入格式

输入第一行包含一个整数n表示数列长度。 第二行包含n个整数a1, a2, ... , an，表示数列中的数。 第三行包含一个整数m表示询问次数。 接下来m行描述询问，其中第i行包含三个整数li, ri, ki表示询问[li, ri]区间内有多少数出现了ki次。 对于20% 的评测用例，n;m ≤ 500, 1 ≤ a1; a2; ... ; an ≤ 1000； 对于40% 的评测用例，n;m ≤ 5000； 对于所有评测用例，1 ≤ n;m ≤ 100000, 1 ≤ a1; a2; ... ; an ≤ 100000, 1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ n。

输出格式

输出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