区间计数查询

题目描述

给定长度为 $N$ 的序列 $A=(A_1,\ldots,A_N)$。

回答 $Q$ 个以下格式的查询。

给定整数 $L$、$R$ 和 $X$。 求 $A_L, \ldots, A_R$ 中值等于 $X$ 的元素个数。

输入格式

输入按以下格式从标准输入给出：

N
A_1 A_2 … A_N
Q
Query_1
Query_2
⋮
Query_Q

其中,$\mathrm{Query}_i$ 表示第 $i$ 个查询。

每个查询按以下格式给出：

L R X

输出格式

输出 $Q$ 行,第 $i$ 行输出第 $i$ 个查询的答案。

样例

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

2
0
0
1

在第一个查询中,$(A_1,A_2,A_3,A_4,A_5) = (3,1,4,1,5)$ 中有两个元素的值等于 $1$。

在第二个查询中,$(A_2,A_3,A_4) = (1,4,1)$ 中没有元素的值等于 $3$。

数据范围

• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq N$
• $1 \leq Q \leq 2\times 10^5$
• 每个查询满足 $1\le L \leq R \leq N$,$1 \leq X \leq N$。
• 输入中的所有值都是整数。