/*
    Mbak Sana Dong
    Mbak Chaeyoung Dong
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int arr[500500], bit[500500], sana[500500], last[500500];
vector<pair<int,int> > vi[500500];
void add(int x, int val)
{
    for(x;x<=500000;x+=(x&-x)) bit[x] += val;
}
int get(int x)
{
    int res = 0;
    for(x;x>0;x-=(x&-x)) res += bit[x];
    return res;
}
int main()
{
    int n,i,j,k,x,y,ans,curr,temp,m;
    int tc;
    int q;
    cin >> n >> q;
    for(i=1;i<=n;i++) {
        scanf("%d", &arr[i]);
    }
    for(i=1;i<=q;i++) {
        cin >> x >> y;
        vi[y].push_back({i, x});
    }
    for(i=1;i<=n;i++) {
        int now = arr[i];
        if(last[now] > 0) {
            add(last[now], -1);
        }
        last[now] = i;
        add(i, 1);
        for(auto x : vi[i]) {
            sana[x.first] = get(i) - get(x.second - 1);
        }
    }
    for(i=1;i<=q;i++) cout << sana[i] << endl;
    return 0;
}
