#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 100005;

int ans[N], i, query, aib[N], n, x, Last[N], k, j;

struct interog
{
    int x,y,ind;
};
interog q[N];
struct pqq
{
    int x,y;
};
pqq a[N];

bool cmp0(pqq a, pqq b)
{
    return (a.y<b.y);
}
bool cmp(interog a, interog b)
{
    return (a.y<b.y);
}

int ub(int x)
{
    return (x&(-x));
}
void upd(int p, int x)
{
    for(; p; p-=ub(p)) aib[p] = max(aib[p], x);
}
int que(int p)
{
    int ans = 0;
    for(; p<=n; p+=ub(p)) ans = max(ans, aib[p]);
    return ans;
}
int main()
{
    freopen("pq.in", "r", stdin);
    freopen("pq.out", "w", stdout);

    scanf("%d%d", &n, &query);

    for(i=1; i<=n; ++i)
    {
         scanf("%d", &x);
         if(Last[x]) a[++k].x = Last[x], a[k].y = i;
         Last[x] = i;
    }
    sort(a+1, a+k+1, cmp0);

    for(i=1; i<=query; ++i)
    {
         scanf("%d%d", &q[i].x, &q[i].y);
         q[i].ind=i;
    }

    sort(q+1, q+query+1, cmp);

    j=1;
    for(i=1; i<=query; ++i)
    {
         while(j<=k && a[j].y<=q[i].y)
            upd(a[j].x, a[j].y-a[j].x+1), j++;

         ans[q[i].ind] = que(q[i].x);
    }

    for(i=1; i<=query; ++i) printf("%d\n", ans[i]-1);

    return 0;
}