问题描述

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ 以及 $Q$ 组询问，每组询问包括三个整数 $L, R, X$。

请你求出在子区间 $A_L, A_{L+1}, \ldots, A_R$ 中，值等于 $X$ 的元素有多少个。

输入格式

第一行输入一个正整数 $N$。

第二行输入 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

第三行输入一个正整数 $Q$。

接下来输入 $Q$ 行，每行包含三个整数 $L, R, X$，表示一组询问。

输出格式

输出共 $Q$ 行，每行一个整数，第 $i$ 行输出第 $i$ 组询问的答案。

样例输入 1

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

样例输出 1

2
0
0
1

说明

样例 1 解释：

• 询问 $1$（$L=1, R=5, X=1$）：区间 $[3, 1, 4, 1, 5]$ 中值为 $1$ 的元素有 $2$ 个；
• 询问 $2$（$L=2, R=4, X=3$）：区间 $[1, 4, 1]$ 中值为 $3$ 的元素有 $0$ 个；
• 询问 $3$（$L=1, R=5, X=2$）：区间 $[3, 1, 4, 1, 5]$ 中值为 $2$ 的元素有 $0$ 个；
• 询问 $4$（$L=1, R=3, X=3$）：区间 $[3, 1, 4]$ 中值为 $3$ 的元素有 $1$ 个。

评测数据规模

对于所有评测数据：

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq N \quad (1 \leq i \leq N)$
• $1 \leq Q \leq 10^5$
• $1 \leq L \leq R \leq N$
• $1 \leq X \leq N$
• 所有输入均为整数