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
import sys
input = sys.stdin.buffer.readline

N, Q = map(int, input().split())
Color = [0] + list(map(int, input().split()))
Query =[]
for i in range(Q):
    l, r = map(int, input().split())
    Query.append(r * 10 ** 12 + l * 10 ** 6 + i)
Query.sort()
Ans = [0] * Q

BIT = [0] * (N + 1)  # BITを使う


def BIT_query(idx):  # idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):  # idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return


cn = max(Color)
Last = [-1] * cn

cnt = 0
for q in Query:
    r = q // 10 ** 12
    l = (q % 10 ** 12) // 10 ** 6
    i = q % 10 ** 6
    while cnt < r:
        cnt += 1
        c = Color[cnt] - 1
        if Last[c] == -1:
            Last[c] = cnt
            BIT_update(cnt, 1)
        else:
            x = Last[c]
            BIT_update(x, -1)
            Last[c] = cnt
            BIT_update(cnt, 1)
    Ans[i] = BIT_query(r) - BIT_query(l-1)

for a in Ans:
    print(a)