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
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        #A1 ... AnのBIT(1-indexed)
        self.BIT = [0] * (n + 1)

    #A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    #Ai += x O(logN)
    def add(self, idx, x):
        while idx <= n:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

n, q = map(int, input().split())
a = list(map(int, input().split()))
pi = [-1] * (n + 1)  # 各数について最後に出てきた場所
ps = [[] for i in range(n)]

for i in range(n):
    l = pi[a[i]]
    if l != -1:
        ps[l].append(i)
    pi[a[i]] = i

qs = [[] for i in range(n)]
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r, i))

d = BIT(n)
ans = [0] * q

for x in range(n - 1, -1, -1):
    for y in ps[x]:
        d.add(y, 1)
    
    for r, i in qs[x]:
        ans[i] = (r - x + 1) - d.query(r)

print(*ans)
    