#include<bits/stdc++.h>
#define ll                      long long 
#define vll                     vector<ll>
#define pb                      push_back
#define MOD                     1000000007
#define ld                      long double
#define vpll                    vector<pair<ll,ll>>
#define vll                     vector<ll>
#define pll                     pair<ll,ll>
#define pld                     pair<ll,ld>
#define all(x)                  x.begin(),x.end()
#define fi                      first
#define se                      second
#define ln                      cout<<"\n";
#define test                    ll T;cin>>T;while(T--)
#define fastIO                  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
ll gcd(ll a,ll b){if(a<b)return gcd(b,a);else if(b==0)return a;else return gcd(b,a%b);}
bool isprime(ll n){for(ll i=2;i*i<=n;i++)if(n%i==0)return 0;return 1;}
ll pow(ll b,ll e){if(e==0)return 1;else if(e%2==0){ll a=pow(b,e/2);return a*a;}else {ll a=pow(b,e/2);return b*a*a;}}
ll powm(ll x,ll y,ll m=MOD){x=x%m;ll res=1;while(y){if(y&1)res=res*x;res%=m;y=y>>1;x=x*x;x%=m;}return res;}
ll lcm(ll a,ll b){ return (a*b)/gcd(a,b);}
ll modInverse(ll a, ll m) { return powm(a, m-2, m);}
bool issq(ll n){ ll p=sqrt(n);return p*p==n;}
ll MIN(ll a=2e18,ll b=2e18,ll c=2e18,ll d=2e18,ll e=2e18){return min(a,min(b,min(c,min(d,e))));}
ll MAX(ll a=-2e18,ll b=-2e18,ll c=-2e18,ll d=-2e18,ll e=-2e18){return max(a,max(b,max(c,max(d,e))));}
vector<int> prime;// if i==prime[i] then prime otherwise smallest prime factor of that number
void seive(ll n){
prime.resize(n+5,0);ll j;for(ll i=2;i<=n;i++){if(!prime[i]){prime[i]=i;for(j=i*i;j<=n;j+=i)if(!prime[j])prime[j]=i;}}}
ll extended_GCD(ll a ,ll b ,ll &x ,ll &y){
    if(a == 0){
        x = 0;
        y = 1;
        return b;
    }
    ll x1 , y1;
    ll gcd = extended_GCD(b%a , a , x1 , y1);
    x = y1 - (b/a)*x1; 
    y = x1;
    return gcd;
}
ll mulInv(ll a , ll mod){
    ll x , y;
    extended_GCD(a , mod , x , y);
    if(x < 0) x += mod;
    return x;
}
void __print(int x) {cout << x;}
void __print(long x) {cout << x;}
void __print(long long x) {cout << x;}
void __print(unsigned x) {cout << x;}
void __print(unsigned long x) {cout << x;}
void __print(unsigned long long x) {cout << x;}
void __print(float x) {cout << x;}
void __print(double x) {cout << x;}
void __print(long double x) {cout << x;}
void __print(char x) {cout << "'" << x << "'";}
void __print(const char *x) {cout << '"' << x << '"';}
void __print(const string &x) {cout << '"' << x << '"';}
void __print(bool x) {cout << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cout << '{'; __print(x.first); cout << ','; __print(x.second); cout << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cout << '{'; for (auto &i: x) cout << (f++ ? "," : ""), __print(i); cout << "}";}
void _print() {cout << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cout << ", "; _print(v...);}
class BIT //1-indexed
{
    public:
        vll BIT,arr;
    public:void update(ll idx,ll delta,ll n)
    {
        while(idx<=n)
        {
            BIT[idx] += delta;
            idx += (idx &(-idx));
        }
    }
    public:ll query(ll idx)
    {
        ll sum = 0;
        while(idx>0)
        {
            sum += BIT[idx];
            idx -= (idx &(-idx));
        }
        return sum;

    }
    public:void init(ll n,ll a[])
    {
        BIT.resize(n+1),arr.resize(n+1,0);
        for(ll i=1;i<=n;i++)
        {
            arr[i]=a[i];
            update(i,a[i],n);
        }
    }

};
ll BSZ = 1;
struct query
{
    ll l,r,idx,bl;
};
bool cmp(query q1,query q2)
{

    if(q1.bl<q2.bl or(q1.bl==q2.bl and((q1.bl&1)==0 and q1.r < q2.r  or((q1.bl&1)==1 and q1.r>q2.r))))
        return 1;
    return 0;
}
ll mp[1000001];
int main()
{

#ifdef LOCAL
	auto start_time = clock();
	#define debug(x...) cout << "[" << #x << "] = ["; _print(x)
#else
	#define debug(x...)
	fastIO; 
#endif
    ll n,q;cin>>n>>q;
    BSZ = sqrt(q);
    if(BSZ>100)
        BSZ += 80;
    ll a[n+1]={};
    for(ll i=1;i<=n;i++)
        cin>>a[i];
    vector<struct query> v(q);
    for(ll i=0;i<q;i++)
    {
        cin>>v[i].l>>v[i].r;
        v[i].idx = i;
        v[i].bl = v[i].l/BSZ;
    }
    ll ans[q+1]={};
    sort(all(v),cmp);
    ll num = 0, curl = 0,curr = 0;
    for(auto x:v)
    {
        while(curr<x.r)
        {
            curr++;
            mp[a[curr]]+=1;
            if(mp[a[curr]] == 1)
            	num++;
        }
        while(curr>x.r)
        {
            mp[a[curr]]-=1;

            if(mp[a[curr]] == 0)
            	num--;
            curr--;
        }
        while(curl<x.l-1)
        {
            curl++;

            mp[a[curl]]-=1;

            if(mp[a[curl]] == 0)
            	num--;
        }
        while(curl>x.l-1)
        {
            mp[a[curl]]+=1;

            if(mp[a[curl]] == 1)
            	num++;
            curl--;
        }
        ans[x.idx]=num;
    }
    for(ll i=0;i<q;i++)
        cout<<ans[i],ln;
#ifdef LOCAL
auto end_time = clock();
cout << "Execution time: " << (end_time - start_time) * (int)1e3 / CLOCKS_PER_SEC << " ms\n";
#endif
return 0;
}

Measured memory_bytes: 31136