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
#include<bits/stdc++.h>
#define mxn 500005
#define xx first
#define yy second
using namespace std;
int lst[mxn], seg[mxn];
void add(int x, int n, int v)
{
    while(x<=n)
    {
        seg[x]+= v;
        x+= (x&-x);
    }
    return;
}
int query(int x)
{
    int ret= 0;
    while(x>0)
    {
        ret+= seg[x];
        x-= (x&-x);
    }
    return ret;
}
typedef pair<int, int>pi;
pi rng[mxn];
vector<pi>vec;
int res[mxn], ara[mxn];
int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++)scanf("%d", &ara[i]);
    for(int i=0; i<q; i++)
    scanf("%d %d", &rng[i].xx, &rng[i].yy), vec.push_back({ rng[i].yy, i });
    sort(vec.begin(), vec.end());
    for(int i=1, j=0; i<=n && j<vec.size(); i++)
    {
        add(i, n, 1);
        if(lst[ ara[i] ])add(lst[ ara[i] ], n, -1);
        lst[ ara[i] ]= i;
        while(vec[j].xx==i)
        {
            res[ vec[j].yy ]= query(rng[ vec[j].yy ].yy)-query(rng[ vec[j].yy ].xx-1);
            j++;
        }
    }
    for(int i=0; i<q; i++)printf("%d\n", res[i]);
    return 0;
}
