#include <iostream>
#include <map>
#include <cstdio>
#include <string>
#include <set>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>

using namespace std;

int N, Q, last[100010], lungime[10010], answer[100010];
vector<pair<int, int> > interval[100010];

int arbInt[400010];
int arbSz;

void putSize(int N) {
    int p = 1;
    while(p<N)
        p<<=1;
    arbSz = p;
}

void update(int pos, int x) {
    pos += arbSz - 1;
    //if(arbInt[pos] > x) return;
    arbInt[pos] = x;
    pos >>= 1;
    while(pos) {
        arbInt[pos] = max(arbInt[pos << 1], arbInt[(pos<<1) + 1]);
        pos >>=1;
    }
}

int query(int left, int right) {
    left += arbSz -1;
    right += arbSz - 1;
    int res = max(arbInt[left], arbInt[right]);
    left = (left + 1) >> 1;
    right = (right - 1) >> 1;
    while(left <= right) {
        res = max(res, max(arbInt[left], arbInt[right]));
        left = (left + 1) >> 1;
        right = (right - 1) >> 1;
    }
    return res;
}

int main()
{
    freopen("pq.in", "r", stdin);
    freopen("pq.out", "w", stdout);
    scanf("%d%d", &N, &Q);
    putSize(N);
    int x,y;
    for(int i = 1; i<= N; i++)
    {
        scanf("%d", &x);
        if(last[x])
            lungime[last[x]] = i - last[x];
        last[x] = i;
    }
    for(int i = 1; i <= N; i++)
    {
        scanf("%d%d", &x, &y);
        interval[x].push_back(make_pair(y, i));
    }
    for(int i = 1; i <= N; i++)
    {
        if(lungime[i])
            update(i + lungime[i], lungime[i]);
    }
    for(int i = 1; i <= N; i++)
    {
        for(int j = 0; j < interval[i].size(); j++)
        {
            answer[interval[i][j].second] = query(i, interval[i][j].first);
        }
        if(lungime[i])update(i+lungime[i], 0);
    }
    for(int i=1; i<=Q; i++)
        printf("%d\n", (answer[i] ? answer[i] : -1));
}