题目描述

小明把过去 n 天里每天使用的零花钱记录了下来。

过来一段时间之后，妈妈跟小明了解的某几天里零花钱为 k 的天数。

输入格式

第一行一个整数 n，表示 n 天。

第二行 n 个整数 $a_i$，表示每天的花费。

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

接下来 m 行，每行三个数 $s_i，t_i , k_i$，表示妈妈问从 $s_i$ 天 到 $t_i$ 天（闭区间，包含$s_i$ 天 和 $t_i$ 天）的这段时间中，有多少天的零花钱 为 $k_i$ 。

数据范围

1 ≤ n , m ≤ 50000

0 ≤ $a_i$ , $k_i$ ≤ 10

1 ≤ $s_i$ < $t_i$ ≤ n

输出格式

输出 m 行，表示对应每一询问的答案。

样例

10
1 2 2 1 3 2 1 3 3 2
3
1 5 2
2 9 3
3 7 4

2
3
0