#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,q,l,r;
    cin >> n >> q;
    vector<int> a(n);
    for(int i = 0; i < n; i++)
        cin >> a[i];

    for(int i = 0; i < n; i++)
    {
        cin >> l >> r;
        l--;
        r--;
        if(r-l == 1)
        {
            cout << "1\n";
            continue;
        }
        map<int,int> m;
        for(int j = l; j <= r; j++)
        {
            if((a[i]&a[j]) <= (a[i]^a[j]))
            {
                m[a[i]]++;
                m[a[j]]++;
            }
        }
        vector<int> v;
        long long sum = 0, am = 0;
        for(const auto& c:m)
        {
            v.push_back(c.second);
            sum+=c.second;
        }
        sort(v.begin(),v.end());
        reverse(v.begin(),v.end());
        for(int i = 0; i < v.size(); i++){
            am+=v[i];
            if(am*2 == sum){
                cout << (r-l)-(i+1) << "\n";
            }
        }
    }
    return 0;
}