#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;


int main()
{
    int16_t n,q;
    cin >> n >> q;

    vector<int> niz(n);
    map<tuple<int16_t, int16_t>, int16_t> prefiksi;

    for(int16_t i =0;i<n;i++)
    {
        cin >> niz[i];
    }// unos

    for(int16_t i =0;i<n;i++)
    {
        for(int16_t j =i;j<n;j++)
        {
            prefiksi[{i,j}]+=((niz[i]&niz[j])>(niz[i]^niz[j]))+prefiksi[{i,j-1}];
            cout << i << " " << j << " ->" << prefiksi[{i,j}] << "\n";
        }
        cout << endl;
    }

    int16_t pocetak, kraj, maks=0;
    map<tuple<int16_t, int16_t>, int16_t> dupliprefiksi;
    while(q>0)// sva pitanja
    {
        cin >> pocetak >> kraj;
        // nakon svakog unosa idemo da vidimo koj je
        pocetak--;
        kraj--;// gledam sve prefikse izmedju ovih kordinata
        maks=0;
        if(dupliprefiksi[{pocetak,kraj}]>0)
            cout << dupliprefiksi[{pocetak,kraj}];
        else
        {
            for(int16_t i = pocetak;i<=kraj;i++)
            {
                maks=max(maks,prefiksi[{i,kraj}]);// koristim to sto je na nacin koje sam slagao prefikse
                // maskimum je uvek neki prvi prefiks i zadji, zbog sabiranja
            }
            dupliprefiksi[{pocetak,kraj}]=maks;
        }

        cout << maks << "\n";

        q--;
    }

    ;

    return 0;

}