#include <bits/stdc++.h>

using namespace std;

//#define local
#ifdef local

template<class T>
void _E(T x) { cerr << x; }

void _E(double x) { cerr << fixed << setprecision(6) << x; }

void _E(string s) { cerr << "\"" << s << "\""; }

template<class A, class B>
void _E(pair<A, B> x) {
    cerr << '(';
    _E(x.first);
    cerr << ", ";
    _E(x.second);
    cerr << ")";
}

template<class T>
void _E(vector<T> x) {
    cerr << "[";
    for (auto it = x.begin(); it != x.end(); ++it) {
        if (it != x.begin()) cerr << ", ";
        _E(*it);
    }
    cerr << "]";
}

void ERR() {}

template<class A, class... B>
void ERR(A x, B... y) {
    _E(x);
    cerr << (sizeof...(y) ? ", " : " ");
    ERR(y...);
}

#define debug(x...) do { cerr << "{ "#x" } -> { "; ERR(x); cerr << "}" << endl; } while(false)
#else
#define debug(...) 114514.1919810
#endif
#define _rep(n, a, b) for (ll n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (ll n = (a); n >= (b); --n)
#define _for(n, a, b) for (ll n = (a); n < (b); ++n)
#define _rof(n, a, b) for (ll n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db long double
#define eps 1e-3
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
#define pdd pair<db, db>
#define endl "\n"
#define ls ch[now][0]
#define rs ch[now][1]
const ll mod = 998244353;
const ll maxn = 5e5 + 10;


ll qpow(ll a, ll b) {
    ll ret = 1;
    for (; b; a = a * a % mod, b >>= 1) {
        if (b & 1) {
            ret = ret * a % mod;
        }
    }
    return ret;
}

vector<ll> f(maxn), invf(maxn);

ll inv(ll a) {
    return qpow(a, mod - 2);
}

void prework() {
    f[0] = 1;
    _rep(i, 1, maxn - 1) {
        f[i] = f[i - 1] * i % mod;
    }
    invf[maxn - 1] = qpow(f[maxn - 1], mod - 2);
    for (ll i = maxn - 2; i >= 0; i--) {
        invf[i] = invf[i + 1] * (i + 1) % mod;
    }

}

ll C(ll n, ll m) {
    if (n > m || m < 0)return 0;
    if (n == 0 || m == n) return 1;
    ll res = (f[m] * invf[m - n] % mod * invf[n]) % mod;
    return res;
}


int num[maxn],tree[maxn],booll[maxn],nnn[maxn],N,ww;;
//num数组保存原数列，tree树状数组，nnn保存结果
struct tt
{
    int l,r;//左右边界
    int pos;//原位置（因为我们要离线排序后处理）
};
tt ask[maxn];
bool cmp(tt x,tt y)
{
    return x.r<y.r;
    //快排大法好，没有什么是快排解决不来哦
    //实在不行就加上一个cmp
}
int lowbit(int n)
{
    return n&(-n);
    //树状数组核心操作×1
}
void add(int n,int now)
{
    while(n<=N)
    {
        tree[n]+=now;
        n+=lowbit(n);
    }
    //树状数组核心操作×2-->更新操作
}
int sum(int n)
{
    int ans=0;
    while(n!=0)
    {
        ans+=tree[n];
        n-=lowbit(n);
    }
    return ans;
    //树状数组核心操作×3———>查询操作
}
int main()
{
    scanf("%d",&N);
    scanf("%d",&ww);
    for(int i=1;i<=N;i++)
        scanf("%d",&num[i]);

    for(int i=1;i<=ww;i++)
    {
        scanf("%d%d",&ask[i].l,&ask[i].r);
        ask[i].pos=i; //存储初始位置
    }
    sort(ask+1,ask+1+ww,cmp);//按r排序
    int next=1;
    for(int i=1;i<=ww;i++)
    {
        for(int j=next;j<=ask[i].r;j++)
        {
            if(booll[num[j]])
                add(booll[num[j]],-1);
            //之前打过标记，在之前的位置加上-1，保证无重复
            add(j,1);
            booll[num[j]]=j;
        }
        next=ask[i].r+1;
        //更新下一次查询的位置
        nnn[ask[i].pos]=sum(ask[i].r)-sum(ask[i].l-1);
        //按询问编号存储每组询问的结果
    }
    for(int i=1;i<=ww;i++)
        cout<<nnn[i]<<endl;
    return  0;
}

Measured memory_bytes: 25232