#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int,int> pii;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double 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...);}

#ifdef OJ
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define all(x) (x).begin(), (x).end()
#define rsort(x) sort((x).rbegin(), (x).rend())
#define sz(x) ((int)x.size())
#define fori(i, n) for (int i = 0; i < (int)(n); ++i)
#define ford(i, n, e) for (int i = (int)(n); i >= (int)(e); --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
template<typename T> bool mmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
template<typename T> bool mmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; }
#define RETURN(x) do{cout << (x) << '\n'; return 0;}while(0)

const char en = '\n';
const int MOD = 0;
const int MAXN = 5e5+3;
const int INF = 1e9;

int c[MAXN];
vector<pii> v[MAXN];
int lft[MAXN], last[MAXN];
int ans[MAXN];

int val[MAXN*4];

void update(int node, int left, int right, int i, int newval) {
    if(left == right) {
        assert(left == i);
        val[node] = newval;
        return;
    }

    int m = (left + right) / 2;
    if(i <= m) update(node*2, left, m, i, newval);
    else update(node*2+1, m+1, right, i, newval);

    val[node] = val[node*2] + val[node*2+1];
}

int query(int node, int left, int right, int l, int r) {
    if (r < l) return 0;
    if (r < left || right < l) return 0;

    if (l <= left && right <= r) return val[node];

    int m = (left + right) / 2;
    return query(node*2, left, m, l, min(m,r)) +
            query(node*2+1, m+1, right, max(m+1,l), r);
}


int solve() {
    int n,q; cin >> n >> q;
    fori(i,n) cin >> c[i];
    fori(i,q) {
        int l,r; cin >> l >> r;
        l--; r--;
        v[r].eb(l,i);
    }

    fore(i,1,n) last[i] = -1;
    fori(i,n) {
        lft[i] = last[c[i]];
        last[c[i]] = i;
    }

    fori(i,n) {
        if(lft[i] != -1) 
            update(1,0,n-1,lft[i],0);
        update(1,0,n-1,i,1);
        for(auto p: v[i]) {
            int l = p.fi;
            int qid = p.se;
            ans[qid] = query(1,0,n-1,l,i);
        }
    }

    fori(i,q) cout << ans[i] << en;

    return 0;
} 

int main(int argc, char **argv) {
#ifdef OJ
    freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "wt", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);

    int ntest = 1;
    //cin >> ntest;
    int t = 1;
    fori(test, ntest) {
        //cout << "Case #" << t << ": ";
        solve();
        t++;
    }

    return 0;
}


Measured memory_bytes: 37316