#include <bits/stdc++.h>
#include <random>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
#define ll long long
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define pll pair<ll,ll>
#define ld double
#define pld pair<ld,ld>
#define pii pair<int,int>
#define sqr(a) ((a)*(a))
#define all(v) v.begin(),v.end()

using namespace std;
//using namespace __gnu_pbds;

ll MOD = 998244353;
const ll INF = 1e18;
const ld E = 1e-18;
const ld PI=acos(-1);
mt19937_64 rnd(time(0));
ll p1 = 31, p2 = 37, p3 = 7, p4 = rnd() % 100 + 1, md1 = MOD, md2 = 998244353, md3 = 998244357, md4 = rnd() % 1000000000;

//using ord_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

ll n, m, k, a[500001], ans[500001];

ll binpow(ll h, ll r, ll md = MOD)
{
    ll l = 1;
    while (r)
    {
        if (r & 1) l *= h, l%=md;
        h *= h;
        h %= md;
        r /= 2;
    }
    return l;
}

ll gcd(ll x, ll y)
{
    if (x < y) swap(x, y);
    while (x && y)
    {
        x %= y;
        swap(x, y);
    }
    return x + y;
}

struct node
{
    node *l, *r;
    ll sm;
    node():l(l),r(r),sm(0){};
};

struct persistent_segment_tree
{
    node* root;

    void build(node *h,int l,int r)
    {
        if (l==r) return;
        int w=(l+r)/2;
        h->l=new node();
        h->r=new node();
        build(h->l,l,w);
        build(h->r,w+1,r);
    }

    void build_new_tree(int h)
    {
        root=new node();
        build(root,1,h);
    }

    void update(node *h,int l,int r,int x,int k)
    {
        if (l==r)
        {
            h->sm=k;
            return;
        }
        int w=(l+r)/2;
        if (x<=w) update(h->l,l,w,x,k); else update(h->r,w+1,r,x,k);
        h->sm=h->l->sm+h->r->sm;
    }

    ll get(node* h,int l,int r,int x,int y)
    {
        if (x>y) return 0;
        if (l==x && y==r)
        {
            return h->sm;
        }
        int w=(l+r)/2;
        return get(h->l,l,w,x,min(y,w))+get(h->r,w+1,r,max(x,w+1),y);
    }
};

persistent_segment_tree g;

vector<int> v[500001];

int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //freopen("capitals.in","r",stdin);
    //freopen("capitals.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    g.build_new_tree(n);
    for (int i = n; i > 0; i--)
    {
        v[a[i]].pb(i);
    }
    for (int i = 1; i <= n; i++)
        if (v[i].size()) g.update(g.root, 1, n, v[i].back(), 1);

    vector<pair<pii, int> > vv;
    for (int i = 0; i < q; i++)
    {
        int x, y;
        cin >> x >> y;
        vv.pb(mp(mp(x, y), i));
    }
    sort(all(vv));
    ll l=1;
    for (int i = 0; i < vv.size(); i++)
    {
        while (vv[i].fi.fi>l)
        {
            g.update(g.root,1,n,l,0);
            v[a[l]].pop_back();
            if (v[a[l]].size())
                g.update(g.root,1,n,v[a[l]].back(),1);
            l++;
        }
        ans[vv[i].se]=g.get(g.root,1,n,vv[i].fi.fi,vv[i].fi.se);
    }
    for (int i = 0; i < q; i++) cout << ans[i] << "\n";
    return 0;
}

/*
a-b=k
a+b=m
a=(m+k)/2;
b=(m-k)/2;
*/


Measured memory_bytes: 76240