#include <iostream>
#include <vector>
#include <array>
using namespace std;
int najvecapoz(int a,int x)
{
    if (a == 0) return x;
    else return najvecapoz(a / 2, x + 1);
}
int najvecavrednost(vector<int> a,int n)
{
    int max = 0;
    for (int i = 0; i < n; i++)
        if (max < a[i]) max = a[i];
    return max;
}
int main()
{
    int n, q,t,l,d;
    cin >> n;
    cin >> q;
    vector<int> a;
    vector<int> stepeni;
    vector<int> resenja;
    vector<int> nasaodosad;
    for (size_t i = 0; i < 30; i++)
    {
        nasaodosad.push_back(0);
    }
    for (size_t i = 0; i < 30; i++)
        stepeni.push_back(0);
    for (size_t i = 0; i < n; i++)
    {
        cin >> t;
        a.push_back(najvecapoz(t,-1));
    }
    vector<vector<int>> f;
    vector<int> g;
    for (size_t i = 0; i < 30; i++)
    {
        g.push_back(0);
    }
    for (size_t i = 0; i < n; i++)
    {
        f.push_back(g);
    }
    for (size_t i = 0; i < n; i++)
    {
        nasaodosad[a[i]]++;
        int j = i;
        if(nasaodosad[a[i]] != 1)
        while (j > -1 && f[j][a[i]] == 0)
        {
            if(j == i)
            f[j][a[i]] = nasaodosad[a[i]];
            else
                f[j][a[i]] = nasaodosad[a[i]] - 1;
            j--;       
        }  
        else f[j][a[i]] = nasaodosad[a[i]];

    }
    for (size_t i = 0; i < 30; i++)
    {
        int j = n - 1;
        while (j > -1 && f[j][i] == 0)
        {
            f[j][i] = nasaodosad[i];
            j--;
        }
    }
    /*for (size_t i = 0; i < 30; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            cout << f[j][i] << " ";
        }
        cout << '\n';
    }*/
    for (size_t i = 0; i < q; i++)
    {
        cin >> t;
        l = t - 1;
        cin >> t;
        d = t - 1;
        for (size_t j = 0; j < 30; j++)
        {
            if(l == 0)
                stepeni[j] = f[d][j];
            else
            stepeni[j] = f[d][j] - f[l - 1][j];
        }
        resenja.push_back(najvecavrednost(stepeni, 30));
        for (size_t g = 0; g < 30; g++)
            stepeni[g] = 0;     
    }
    for (size_t i = 0; i < q; i++)
        cout << resenja[i] << '\n';

/*10 5
1 1 8 4 16 4 2 1 1 4 
3 5
1 10
2 5
1 6
5 9*/
}