D - Range Count Query Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。

以下の形式で与えられる Q 個のクエリに答えてください。

  • 整数 L,R,X が与えられる。 A_L, \ldots,A_R のうち、値が X に等しいものの個数を求めよ。

制約

  • 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
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N 
A_1 A_2 \ldots A_N
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

ただし、\mathrm{Query}_ii 個目のクエリを表す。

各クエリは以下の形式で与えられる。

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 個目のクエリでは、 (A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5) のうち値が 1 に等しいものの個数は 2 です。

2 個目のクエリでは、 (A_2,A_3,A_4) =(1,4,1) のうち値が 3 に等しいものの個数は 0 です。

Score : 400 points

Problem Statement

You are given a sequence of length N: A=(A_1,\ldots,A_N).

Answer Q queries given in the following format.

  • You are given integers L, R, and X. Find the number of elements among A_L, \ldots, A_R whose values are equal to X.

Constraints

  • 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, for each query.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N 
A_1 A_2 \ldots A_N
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q

Here, \mathrm{Query}_i represents the i-th query.

Each query is in the following format:

L R X

Output

Print Q lines, the i-th of which contains the answer to the i-th query.


Sample Input 1

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

Sample Output 1

2
0
0
1

In the first query, two of (A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5) have values equal to 1.

In the second query, zero of (A_2,A_3,A_4) =(1,4,1) have values equal to 3.