#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long int
#define ld long double
#define pb push_back
#define pll pair<ll, ll> 
#define tri pair<pll, ll>
#define vl vector<ll> 
#define vvl vector< vector<ll> > 
#define vlp vector< pair<ll, ll> >
#define vllp vector<pair<pll, ll> > 
#define mll map<ll, ll> 
#define rep(i,a)  for(ll i=0; i< a; i++)
#define rep1(i,a)   for(ll i = 1; i< a; i++)
#define foi(i, a, b)    for(ll i = a; i<b ; i++)
#define fod(i, a, b)    for(ll i = a; i>=b ; i--)
#define mp make_pair
#define all(v)  (v).begin(), (v).end()
#define fst first
#define sec second
#define ff first.first
#define fs first.second
#define max3(a, b, c)   max(max(a, b), c)
#define min3(a, b, c)   min(min(a, b), c)
#define MAX 1000005
#define MOD 1000000007
// #define MOD 998244353
#define endl "\n"
#define INF (ll)1e18
#define s(v) (ll)v.size()
#define e(v) v.empty()
#define bscount(x) __builtin_popcountll(x)
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>

using namespace std;
// using namespace __gnu_pbds;

void __print(ll x) {cerr << x;}
void __print(ld x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

ll gcd(ll a, ll b){if(b==0)return a;return gcd(b, a%b);}
ll cpow(ll a, ll b, ll M){ll ans = 1;while(b){if(b&1) ans = ans*a%M; b/=2;a=a*a%M;}return ans;}
void ingraph(vvl& graph, ll m){ll x, y;rep(i, m){cin>>x>>y;x--, y--;graph[x].pb(y);graph[y].pb(x);}}
ll modify(ll n){ll res = n;res%=MOD;res+=MOD;res%=MOD;return res;}
ll fexp(ll a, ll b) {return cpow(a, b, MOD);}
ll cinv(ll a, ll p){return cpow(a, p-2, p);} 
ll inverse(ll a)    {return cinv(a, MOD);}

bool comp(const tri& a, const tri& b){
    return a.fs < b.fs;
}

vl tree(4*MAX);

void upd(ll cur, ll l, ll r, ll pos){
    if(l > pos || r < pos)  return;
    if(l == r && r == pos){
        tree[cur] = 1;return;
    }
    ll mid = (r - l)/2 + l;
    upd(2*cur + 1, l, mid, pos);
    upd(2*cur + 2, mid+1, r, pos);
    tree[cur] = tree[2*cur + 1] + tree[2*cur + 2];
}

ll que(ll cur, ll l, ll r, ll x, ll y){
    if(l > y || r < x)  return 0;
    if(x <= l && r <= y)    return tree[cur];
    ll mid = (r - l)/2 + l;
    return que(2*cur + 1, l, mid, x, y) + que(2*cur + 2, mid+1, r, x, y);
}

int main(){
	// #ifndef ONLINE_JUDGE
 //        freopen("../input.txt", "r", stdin);
 //        freopen("../output.txt", "w", stdout);
 //    #endif
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    ll t;
    // cin>>t/;
    t = 1;
    ll tc = 0;
    while(tc++ < t){
        ll n, q;cin>>n>>q;
        vl vec(n);
        rep(i, n)   cin>>vec[i];
        vl nxt(n);
        mll occ;
        vlp toup;
        fod(i, n-1, 0){
            if(occ.count(vec[i]) == 0)
                nxt[i] = n+1;
            else nxt[i] = occ[vec[i]];
            occ[vec[i]] = i;
            toup.pb({nxt[i], i});
        }
        vllp query;
        ll l, r;
        rep(i, q){
            cin>>l>>r;
            --l, --r;
            query.pb({{l, r}, i});
        }
        sort(all(query), comp);
        reverse(all(query));
        sort(all(toup));reverse(all(toup));
        vl ans(q);
        ll j = 0;
        rep(i, q){
            while(j < n && toup[j].fst > query[i].fs)   upd(0, 0, n-1, toup[j++].sec);
            ans[query[i].sec] = que(0, 0, n-1, query[i].ff, query[i].fs);
        }
        rep(i, q)   cout<<ans[i]<<endl;
    }
}

Measured memory_bytes: 99884