F - Range Set Query

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.

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

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.

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

1
2
2
1
2
2
6
3
3
3