#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXLOG = 18;
const int INF  = 1e9;

int n, q;
struct Sparse
{
    int par[MAXLOG][MAXN];
    void build(int next[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            par[0][i] = next[i];
        }

        for (int lg = 1 ; (1 << lg) <= n ; ++lg)
        {
            for (int u = 1 ; u <= n ; ++u)
            {
                par[lg][u] = par[lg - 1][par[lg - 1][u]];
            }
        }
    }

    int query(int l, int r)
    {
        int ans = 0;
        for (int lg = MAXLOG - 1 ; lg >= 0 ; --lg)
        {
            if (par[lg][l] != 0 && par[lg][l] <= r + 1)
            {
                ans += (1 << lg);
                l = par[lg][l];
            }
        }

        return ans;
    }
};

int a[MAXN];
Sparse sparse;
int next[MAXN];
int hatR[MAXN];

void solve()
{
    int min = n + 2;
    std::fill(hatR + 1, hatR + 1 + n, n + 1);
    for (int i = n ; i >= 1 ; --i)
    {
        min = std::min(min, hatR[a[i]] + 1);
        hatR[a[i]] = i;
        next[i] = min;
    }

    sparse.build(next);
    for (int i = 1 ; i <= q ; ++i)
    {
        int l, r;
        std::cin >> l >> r;
        std::cout << sparse.query(l, r) << '\n';
    }
}

void input()
{
    std::cin >> n >> q;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }
}

void fastIOI()
{
    freopen("matchingseq.in", "r", stdin);
    freopen("matchingseq.out", "w", stdout);
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}