#include <stdio.h>
#include <assert.h>
#include <vector>
#include <stdlib.h>

using namespace std;

#define MAXN 100000
#define MAXT 100000
#define MAXQ 100000

vector<int> g[MAXT];

void init(int t[],int N){
    for(int i=0; i<N; i++){
        g[t[i]].push_back(i);
    }
}

int bs(int t, int k){
    int size = g[t].size();
    int i = 0;
    int f = size-1;

    while(i<f){
        int m = (i+f)/2;
        if(k < g[t][m]){
            f = m-1;
        } else if( k > g[t][m]){
            i = m+1;
        } else
            return 0;
    }

    int a = abs(k-g[t][i]);
    int b = a;
    if(i<size-1)
        b = abs(k-g[t][i+1]);
    int c = a;
    if(i>0)
        c = abs(k-g[t][i-1]);
    if(i==0)
        c = abs(k-g[t][size-1]);

    if(a<b && a<c)
        return a;
    if(a<b && a>c)
        return c;
    return b>c?c:b;
}

void risolvi(int N, int Q, int t[], int a[], int b[], int d[]) {
    init(t,N);

    for (int i=0; i<Q; i++) {
        d[i] = bs(b[i],a[i]);
    }
}


int t[MAXN], a[MAXQ], b[MAXQ], d[MAXQ];

int main() {
    FILE *fr, *fw;
    int N, Q, i;

    fr = fopen("input.txt", "r");
    fw = fopen("output.txt", "w");
    assert(2 == fscanf(fr, "%d%d", &N, &Q));
    for(i=0; i<N; i++)
        assert(1 == fscanf(fr, "%d", &t[i]));
    for(i=0; i<Q; i++)
        assert(2 == fscanf(fr, "%d%d", &a[i], &b[i]));

    risolvi(N, Q, t, a, b, d);

    for(i=0; i<Q; i++)
        fprintf(fw, "%d\n", d[i]);
    fclose(fr);
    fclose(fw);
    return 0;
}