#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second

clock_t time_p = clock();
void time_taken()
{
    time_p = clock() - time_p;
    cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}

const ll mod = 1e9 + 7;
const ll INF = 1e18;

struct BIT
{
    vector<long long> bit;
    BIT(int n = 5e5 + 6) : bit(n)
    {
    }
    void update(int x, int v)
    {
        while (x < int(bit.size()))
        {
            bit[x] += v;
            x += (x & -x);
        }
    }
    long long query(int x)
    {
        long long sum = 0;
        while (x > 0)
        {
            sum += bit[x];
            x -= (x & -x);
        }
        return sum;
    }
    void upd_range(int l, int r, int v)
    {
        update(l, v);
        update(r + 1, -v);
    }
    long long query_range(int l, int r)
    {
        return query(r) - query(l - 1);
    }
};

#define TRACE
#ifdef TRACE
#define trace(...) { cerr<<"[ "; __trace__(#__VA_ARGS__, __VA_ARGS__);}
#undef endl
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const pair<Arg1,Arg2> &x) {
    return out<<"("<<x.first<<","<<x.second<<")";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const vector<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const set<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const map<Arg1,Arg2> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
void __trace__(const string name, Arg1&& arg1){
    cerr << name << " : " << arg1 << " ] " << endl;
}
 
template <typename Arg1, typename... Args>
void __trace__(const string names, Arg1&& arg1, Args&&... args){
    const string name = names.substr(0,names.find(','));
    cerr<<name<<" : "<<arg1<<" | ";
    __trace__(names.substr(1+(int)name.size()), args...);
}
#else
    #define trace(args...)
#endif
 

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vi c(n);
    fori(i, n) cin >> c[i];
    vector<vii> a(n+1);
    fori(i, q)
    {
        int l, r;
        cin >> l >> r;
        --l;
        --r;
        a[r].pb({l,i});
    }
    BIT b;
    vi last(n + 1, -1);
    vi ans(q);
    fori(i, n)
    {
        // trace(i, c[i], last[c[i]]);
        if (last[c[i]] != -1)
        {
            b.update(last[c[i]]+1, -1);
        }
        b.update(i + 1, 1);
        // trace(i, a[i]);
        for (auto q : a[i])
        {
            ans[q.se] = b.query_range(q.fi + 1, i + 1);
        }
        last[c[i]] = i;
    }
    fori(i,q){
        cout << ans[i] << endl;
    }

    time_taken();
    return 0;
}

Measured memory_bytes: 35188