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
N, Q = map(int, input().split())
C = [int(i) for i in input().split()]

pi = [-1]*(N+1)
ps = [[] for _ in range(N+1)]
for i in range(N):
    l = pi[C[i]]
    if l != -1:
        ps[l].append(i)
    pi[C[i]] = i

qs = [[] for _ in range(N+1)]
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r, i))


bit = [0]*(N+1)


def bit_sum(idx):
    res_sum = 0
    while idx > 0:
        res_sum += bit[idx]
        idx -= idx & (-idx)
    return res_sum


def bit_add(idx, x):
    while idx <= N:
        bit[idx] += x
        idx += idx & (-idx)
    return True


ans = [0]*Q
for x in range(N-1, -1, -1):
    for y in ps[x]:
        bit_add(y, 1)
    for r, i in qs[x]:
        ans[i] = r-x+1-bit_sum(r)


for i in range(Q):
    print(ans[i])
