#include        "algorithm"
#include        "iostream"
#include        "numeric"
#include        "iomanip"
#include        "cstring"
#include        "math.h"
#include        "bitset"
#include        "string"
#include        "vector"
#include        "ctime"
#include        "queue"
#include        "stack"
#include        "map"
#include        "set"

#include        "ext/pb_ds/assoc_container.hpp" // Common file
#include        "ext/pb_ds/tree_policy.hpp" // Including tree_order_statistics_node_update
#include        "ext/pb_ds/detail/standard_policies.hpp"

using namespace std;
using namespace __gnu_pbds;


#define          f first
#define          lgn 25
#define          endl '\n'
#define          sc second
#define          N (int)5e5+5
#define          pb push_back
#define          mod 1000000007
#define          ld long double
#define          vi vector<int>
#define          eb emplace_back
#define          vpii vector<pii>
#define          mii map<int,int>
#define          int long long 
#define          pii pair<int,int>
#define          pq priority_queue
#define          test(x) while(x--)
#define          all(x) begin(x),end(x)
#define          allr(x) rbegin(x),rend(x)
#define          fo(i,a,n) for(int i=a;i<n;i++)
#define          rfo(i,n,a) for(int i=n;i>=a;i--)
#define          FAST ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define          time() cerr << "Time : " << (double)clock() / (double)CLOCKS_PER_SEC << "s\n"
#define          PI acos(-1.0)
#define          bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)

typedef tree< int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update > 
OS ;

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

inline void INP()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);   
        freopen("output.txt","w",stdout);
    #endif 
}

const int inf = 0x3f3f3f3f;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int BLOCK = sqrt(N)+1;

int n,m,k,q,res;
int a[N], ans[N], fr[N];

        
struct Q
{
    int l, r, qno;

    bool operator < (const Q&b ) const
    {
        int aBlock = l/BLOCK;
        int bBlock = b.l/BLOCK;

        if( aBlock != bBlock ) return aBlock < bBlock;

        return r < b.r;
    }

}Q[(int)5e5+5];

class MOs
{
    public:

    void inpQ()
    {
        for( int i = 0; i < q; i++)
        {
            cin >> Q[i].l >> Q[i].r;
            Q[i].l; // for both zero based and 1 based
            Q[i].r; // for 0-based
            Q[i].qno = i;
        }
    }

    void add(int pos)
    {
        int no = a[pos];
        fr[no]++;
        if( fr[no] == 1 ) res++;    
    }

    void rmv(int pos)
    {
        int no = a[pos];
        if( fr[no] == 1 ) res--;
        fr[no]--;
    }

    void process()
    {
        int nowL = 0, nowR = 0;

        for(int i = 0; i < q; i++)
        {
            int L = Q[i].l, R = Q[i].r , Qno = Q[i].qno;
            // bug(L,R);

            while( nowL > L ) nowL-- ,add(nowL);
            
            while( nowL < L ) rmv(nowL) , nowL++;

            while( nowR <= R ) add(nowR) , nowR++;

            while( nowR > R+1 ) nowR-- ,rmv(nowR);

            // bug(L,R,res);
            ans[Qno] = res;
        }   
    }

    void stuff()
    {
        inpQ(); // taking queries 
        sort( Q, Q+q); // sorting
        process(); // processing queries
    }
}mo;


void go()
{
    cin >> n >> q;

    fo(i,1,n+1)
    {
        cin >> a[i];
    }
    // cin >> q;
    mo.stuff();
    fo(i,0,q) cout << ans[i] << endl;

}

int32_t main()
{
    // INP(); 
    FAST;     
    int t=1; 
    // cin>>t;
    test(t) go();
}



Measured memory_bytes: 27188