//AUTHOR: RAVAN_2070
//PUNE INSTITUTE OF COMPUTER TECHNOLOGY
/*                                                    
      I ♥ CLARICE STARLING...                                                               
        EXPLAINATION BELOW->
*/
//MO'S ALGORITHM
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vi;
typedef vector<pair<ll,ll>> vii;
typedef pair<ll,ll> pii;
typedef map<ll,ll> mii;
#define MOD7 1000000007
#define MOD9 1000000009
#define pi 3.1415926535
#define Test_cases ll TC;cin>>TC;while(TC--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(), x.rend()
#define sp(x) fixed<<setprecision(x)
#define sz(x) (ll)(x.size())
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
const ll INF = (ll)2e18 + 77;
int BLOCK_SIZE;
const int N=(int)5e5+5;
int f[N],cnt;
vector<int>c;
bool compare(pair<int,int>a,pair<int,int>b)
{
    if(a.F/BLOCK_SIZE!=b.F/BLOCK_SIZE)return a<b;
    else return (a.F/BLOCK_SIZE&1)?(a.S<b.S):(a.S>b.S);
}
struct Query
{
    int l,r,idx;
    bool operator<(Query other)
    {
        return compare(mp(l,r),mp(other.l,other.r));
    }
};
void add(int i)
{
    f[c[i]]++;
    if(f[c[i]]==1)cnt++;
}
void remove(int i)
{
    f[c[i]]--;
    if(f[c[i]]==0)cnt--;
}
int get_ans()
{
    return cnt;
}
void mo(vector<Query>&V)
{
    vector<int>ans(sz(V));
    int cur_l,cur_r,i;
    cur_l=0;cur_r=-1;
    for(Query & q: V)
    {
        while(cur_l>q.l)
        {
            cur_l--;
            add(cur_l);
        }
        while(cur_l<q.l)
        {
            remove(cur_l);
            cur_l++;
            
        }
        while(cur_r<q.r)
        {
            cur_r++;
            add(cur_r);
        }
        while(cur_r>q.r)
        {
            remove(cur_r);
           cur_r--; 
        }
        ans[q.idx]=get_ans();
    }
    
    fo(i,0,sz(V))cout<<ans[i]<<"\n";
}
void solve()
{
    int n,q,i;cin>>n>>q;
    c=vector<int>(n);
    BLOCK_SIZE=sqrt((double)n);
    fo(i,0,n)cin>>c[i];
    
    vector<Query>V(q);
    fo(i,0,q)
    {
        cin>>V[i].l>>V[i].r;
        V[i].l--;V[i].r--;
        V[i].idx=i;
    }
    sort(all(V));
    mo(V);
    
}
int main()
{
   fastio
  // Test_cases
   solve();
  return 0;
}
//**always check if you are not killing input in between
//map<ll,ll,greater<int>> to sort in descending order ,in iterator declaration no greater<int>
//if you want to apply lowerbound on set use s.lower_bound(key),not the one used for vector
// Syntax to create a min heap for priority queue priority_queue <int, vector<int>, greater<int>>; 
//for modinverse use modularexponention(x,M-2,M);
//for "each" subtraction from ans(ans-k) if(ans<0) do ans+=MOD,ans%=MOD
//vector<vector<int>>dp(201,vector<int>(n+1)); A way to initialize vector of vector
//string2=string1.substr(pos,length);if len no specified then till end
//void fill (ForwardIterator first, ForwardIterator last, const T& val);
//The range filled is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.


//If wrong on pretest 2 means logically wrong
/* TIPS FOR DEBUGGING
 * Check if values are not overflowing (use long long where required)
 * Check if ranges are inclusive or not.
 * Check properly if greedy will work or not before using it.
 * Check EDGE CASES!! Seriously, even in 2B, saving 8 points by being
 * 2 minutes faster will bite you in the ass if you don't make sure
 * it works on edge cases.
 * Keep adding to this list.
*/


Measured memory_bytes: 15488