Home

Contest: Task: Related: TaskE TaskG

Score : $600$ points

Problem Statement

We have $N$ colored balls arranged in a row from left to right; the color of the $i$-th ball from the left is $c_i$.

You are given $Q$ queries. The $i$-th query is as follows: how many different colors do the $l_i$-th through $r_i$-th balls from the left have?

Constraints

  • $1\leq N,Q \leq 5 \times 10^5$
  • $1\leq c_i \leq N$
  • $1\leq l_i \leq r_i \leq N$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $Q$
$c_1$ $c_2$ $\cdots$ $c_N$
$l_1$ $r_1$
$l_2$ $r_2$
$:$
$l_Q$ $r_Q$

Output

Print $Q$ lines. The $i$-th line should contain the response to the $i$-th query.

Sample Input 1

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

Sample Output 1

2
3
1
  • The $1$-st, $2$-nd, and $3$-rd balls from the left have the colors $1$, $2$, and $1$ - two different colors.
  • The $2$-st, $3$-rd, and $4$-th balls from the left have the colors $2$, $1$, and $3$ - three different colors.
  • The $3$-rd ball from the left has the color $1$ - just one color.

Sample Input 2

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

Sample Output 2

1
2
2
1
2
2
6
3
3
3