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
class BIT():
    def __init__(self,n):
        self.BIT=[0]*(n+1)
        self.num=n

    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 update(self,idx,x):
        while idx <= self.num:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
c=list(map(int,input().split()))
query=[]
for i in range(Q):
    l,r=map(int,input().split())
    query.append((l,r,i))

query.sort(key=lambda x:-x[1])
ans=[0]*Q
last=[0 for i in range(N)]
B=BIT(N)
for i in range(N):
    val=c[i]-1
    if last[val]!=0:
        B.update(last[val],-1)
    last[val]=i+1
    B.update(i+1,1)
    while query and query[-1][1]==i+1:
        l,r,id=query.pop()
        res=B.query(r)-B.query(l-1)
        ans[id]=res

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