#include <bits/stdc++.h>

using namespace std;
vector <vector <int>> v(1000000);

void bits(int x, int j)
{
        for (int i=0; i<32; i++) // ovaj zadatak je skem
        {
            if ((x==1 && i == 0) || (x == 2 && i == 1) || (x == 3 && i == 1)  || 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;
    for (int i=0; i<n; i++)
    {
        cin >> x;
        bits(x, i);
    }
    //cout << " j";
    /*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 j=0; j<32; j++)
            if (maks < v[j][r-1]-v[j][l-1])
                maks=v[j][r-1]-v[j][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;
    }*/


}