E - 花の種類を数えよう 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は植物園の管理人として働いています。植物園には一直線に並んだ N 個の花壇があり、左から順に 1, 2, \ldots, N の番号が付けられています。各花壇 i (1 \leq i \leq N) には、品種番号 P_i の花が植えられています。品種番号は 1 以上 N 以下の整数であり、異なる花壇に同じ品種番号の花が植えられていることもあります。

植物園では Q 回の見学ツアーが予定されています。i 回目 (1 \leq i \leq Q) のツアーでは、花壇 L_i から花壇 R_i までの範囲（両端を含む）を見学します。

高橋君は、各ツアーの案内を準備するために、見学範囲内に何種類の花があるかを事前に把握しておきたいと考えています。

各ツアーについて、花壇 L_i から花壇 R_i の範囲に含まれる異なる品種番号の数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq P_i \leq N (1 \leq i \leq N)
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
  • 入力はすべて整数

入力

N Q
P_1 P_2 \ldots P_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • 1 行目には、花壇の数を表す整数 N と、ツアーの回数を表す整数 Q が、スペース区切りで与えられる。
  • 2 行目には、各花壇に植えられている花の品種番号を表す整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
  • 続く Q 行では、各ツアーの見学範囲が与えられる。
  • そのうち i 行目 (1 \leq i \leq Q) には、i 回目のツアーにおける見学範囲の左端 L_i と右端 R_i が、スペース区切りで与えられる。

出力

Q 行にわたって出力せよ。i 行目 (1 \leq i \leq Q) には、i 回目のツアーにおいて、花壇 L_i から花壇 R_i の範囲に含まれる異なる品種番号の数を出力せよ。

入力例 1

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

出力例 1

2
3
3

入力例 2

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

出力例 2

4
5
7
1
6

入力例 3

20 8
5 3 5 2 1 4 3 2 1 5 4 3 2 1 5 4 3 2 1 4
1 20
1 1
10 15
5 10
1 10
11 20
7 14
3 8

出力例 3

5
1
5
5
5
5
5
5

Score : 466 pts

Problem Statement

Takahashi works as a caretaker at a botanical garden. The garden has N flower beds arranged in a straight line, numbered 1, 2, \ldots, N from left to right. Each flower bed i (1 \leq i \leq N) contains a flower of species number P_i. Species numbers are integers between 1 and N inclusive, and different flower beds may contain flowers of the same species number.

The botanical garden has Q tour visits scheduled. The i-th tour (1 \leq i \leq Q) visits the range from flower bed L_i to flower bed R_i (inclusive).

Takahashi wants to know in advance how many distinct types of flowers are in each tour's visiting range, in order to prepare the guide for each tour.

For each tour, determine the number of distinct species numbers contained in the range from flower bed L_i to flower bed R_i.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • 1 \leq P_i \leq N (1 \leq i \leq N)
  • 1 \leq L_i \leq R_i \leq N (1 \leq i \leq Q)
  • All inputs are integers

Input

N Q
P_1 P_2 \ldots P_N
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q
  • The first line contains an integer N representing the number of flower beds and an integer Q representing the number of tours, separated by a space.
  • The second line contains integers P_1, P_2, \ldots, P_N representing the species numbers of the flowers planted in each flower bed, separated by spaces.
  • The following Q lines give the visiting range for each tour.
  • The i-th of these lines (1 \leq i \leq Q) contains the left endpoint L_i and right endpoint R_i of the visiting range for the i-th tour, separated by a space.

Output

Output Q lines. The i-th line (1 \leq i \leq Q) should contain the number of distinct species numbers in the range from flower bed L_i to flower bed R_i for the i-th tour.

Sample Input 1

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

Sample Output 1

2
3
3

Sample Input 2

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

Sample Output 2

4
5
7
1
6

Sample Input 3

20 8
5 3 5 2 1 4 3 2 1 5 4 3 2 1 5 4 3 2 1 4
1 20
1 1
10 15
5 10
1 10
11 20
7 14
3 8

Sample Output 3

5
1
5
5
5
5
5
5