Range Set Query

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.

Examples

Input

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

Output

2 3 1

Input

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

Output

1 2 2 1 2 2 6 3 3 3

inputFormat

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

outputFormat

Output

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

Examples

Input

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

Output

2 3 1

Input

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

Output

1 2 2 1 2 2 6 3 3 3

样例

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

2
3
1

</p>