#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
const int N=5e5+50,lg=30;
int n,q,a[N],res[N];
array<int,3>Qs[N];
struct BIT{
    int T[N+5];
    void Update(int i,int x){for(;i<=N;i+=i&-i)T[i]+=x;}
    int Get(int i){int x=0;for(;i>=1;i-=i&-i)x+=T[i];return x;}
    int Get(int l,int r){return Get(r)-Get(l-1);}
    void Clear(){for(int i=0;i<=N;i++)T[i]=0;}
}bt;
int main(){
    scanf("%i%i",&n,&q);
    for(int i=1;i<=n;i++)scanf("%i",&a[i]);
    for(int i=1;i<=q;i++){
        int l,r;scanf("%i%i",&l,&r);
        Qs[i]={l,r,i};
    }
    for(int j=0;j<=lg;j++){
        for(int i=1;i<=n;i++){
            if(a[i]==1)bt.Update(i,1);
            a[i]>>=1;
        }
        for(int i=1;i<=q;i++){
            res[Qs[i][2]]=max(res[Qs[i][2]],bt.Get(Qs[i][0],Qs[i][1]));
        }
        bt.Clear();
    }
    for(int i=1;i<=q;i++)printf("%i\n",res[i]);
    return 0;
}