#include <bits/stdc++.h>

using namespace std;
vector <vector<int>> v (32, {1000000, 0});

void bits(int x, int j)
{
        for (int i=0; i<32; i++)
        {
            if ((x==1 && i == 0) || (x == 2 && i == 1) || (x == 3 && i == 2)  || i == (int)log(x)+1)
                if (j==0)
                    v[i][j]=1;
                else
                    v[i][j]=v[i][j-1]+1;
            else
                if (j==0)
                    v[i][j]=0;
                else
                    v[i][j]=v[i][j-1];
        }
}


int main()
{
    int n, q, x, mx;
    cin >> n >> q;
    vector <int> ans(n);
    for (int i=0; i<n; i++)
    {
        cin >> x;
        if ((int)log (x)+1 > mx)
            mx=(int) log(x)+1;
        bits(x, i);
    }
    /*for (int i=0; i<n; i++)
    {
        for (int j =0; j<n; j++)
            cout << v[j][i];
        cout << endl; }*/
    for (int i=0; i<q; i++)
    {
        int l, r, maks=0;
        cin >> l >> r;
        for (int i=0; i<mx; i++)
            if (maks < v[i][r-1]-v[i][l-1])
                maks=v[i][r-1]-v[i][l-1];
        cout << maks << endl;

    }
    /*for (int i=0; i<n; i++)
    {
     for (int j=0; j<n; j++)
            cout << v[j][i];
    cout << endl;
    }*/


}