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
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            try:
                if mp[da[now]]!=-1:
                    fw.add(mp[da[now]], -1)
                mp[da[now]] = now
            except:
                pass
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

    print '\n'.join(map(str, ans))


            

 
 
 
 
my_main()