#include <bits/stdc++.h>

using namespace std;

long long n,q;
    vector<long long> v;
bool moze(long long k,long long l,long long r){
long long br=0,tmp=0;
for(long long i=l; i<=r; i++){
    tmp=0;
    long long j=i+1;
    for(j=i+1; j<=r; j++)
        if((v[i]&v[j]>v[i]^v[j]))tmp++;
        else {break;}
    if(j==r)br+=tmp;
}

if(br>=k*(k-1)/2)return true;
return false;
}

int main()
{
    cin >> n >> q;v.resize(n);
    bool stepen2=true;
    for(long long i=0; i<n; i++){cin >> v[i];if(1<<(31-__builtin_clz(v[i]))!=v[i])stepen2=false;}
    if(stepen2){
    while(q--){
            long long l,r;cin >> l >> r;
            cout << "uso" << r-l+1 << endl;
        }
    }
    else if(n<=10 and q<=10){
        while(q--){
            long long l,r;cin >> l >> r;
            l--;r--;
            if(l==r-1){cout << "1" <<endl;continue;}
            long long k1=0,k2=(r-l+1),mid=k1+(k2-k1)/2,ans=0;
            while(k1<=k2){
                mid=k1+(k2-k1)/2;
                if(moze(mid,l,r)){ans=mid;k1=mid+1;}
                else k2=mid-1;
            }
            cout << ans << endl;
        }
    }

    return 0;
}