#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int A [100005];
vector <int> V [100005];
vector <int> used;
bool used_bool [100005];

int bin_search (int row, int val1, int val2, int INF, int SUP)
{
    if (SUP < INF) return -2;
    int mid = (INF + SUP) / 2;
    if (V [row] [mid] >= val1 && V [row] [mid] <= val2) return mid;
    if (V [row] [mid] < val1) return bin_search (row, val1, val2, mid + 1, SUP);
    if (V [row] [mid] > val2) return bin_search (row, val1, val2, INF, mid - 1);
}

int main()
{
    ifstream f ("pq.in");
    ofstream g ("pq.out");

    int N, Q, i, j, val1, val2, poz, row, k, costmax, costcrt;
    f >> N >> Q;

    for (i = 1; i <= N; ++ i)
    {
        f >> A [i];
        V [A [i]] . push_back (i);
        if (!used_bool [A [i]])
        {
            used_bool [A [i]] = 1;
            used . push_back (A [i]);
        }
    }

//    for (i = 0; i <= 7; ++ i)
//    {
//        cout << i << ": ";
//        for (j = 0; j < V [i] . size (); ++ j)
//        {
//            cout << V [i] [j] << " ";
//        }
//        cout << "\n";
//    }
//
//    for (i = 0; i < used . size (); ++ i)
//        cout << used [i] << " ";
//    cout << "\n";

    for (i = 1; i <= Q; ++ i)
    {
        costmax = -1231312;

        f >> val1 >> val2;

        for (j = 0; j < used . size (); ++ j)
        {
            row = used [j];
            poz = bin_search (row, val1, val2, 0, V[row].size ());

//            cout << row << ": " << poz << "\n";

            if (poz != -2)
            {
                if (poz > 0)
                {
                    k = poz;
                    while (V [row] [k - 1] >= val1)
                    {
                        costcrt = V [row] [k] - V [row] [k - 1];
                        if (costcrt > costmax) costmax = costcrt;
                        k --;
                        if (k <= 0) break;
                    }
                }
                if (poz < V [row] . size () - 1)
                {
                    k = poz;
                    while (V [row] [k + 1] <= val2)
                    {
                        costcrt = V [row] [k + 1] - V [row] [k];
                        if (costcrt > costmax) costmax = costcrt;
                        k ++;
                        if (k >= V [row] . size () - 1) break;
                    }
                }
            }
        }

        if (costmax == -1231312) g << "-1";
        else g << costmax;
        g << "\n";
    }

    return 0;
}