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

    for(int i = 0; i < n; i++)
        for(int j = i; j < n; j++)
            if((a[i]&a[j]) <= (a[i]^a[j]))
                p.push_back({min(i,j),max(i,j)});
    map<int,int> gg;
    vector<int> g;
    sort(p.begin(),p.end());
    for(int t = 0; t < q; t++){
        gg.clear();
        g.clear();
        cin >> l >> r;
        l--;
        r--;
        if(r-l == 1){
            cout << "1\n";
            continue;
        }
        for(int i = 0; i < p.size(); i++){
            if(p[i].first < l) continue;
            gg[p[i].first]++;
            gg[p[i].second]++;
        }
        int sum = 0;
        for(const auto& temp:gg){
            g.push_back(temp.second);
            sum+=temp.second;
        }
        if(g.size() == 0){
            cout << (r-l) << "\n";
            continue;
        }
        sort(g.begin(),g.end());
        reverse(g.begin(),g.end());
        int sakup = 0;
        for(int i = 0; i < g.size(); i++){
            sakup+=g[i];
            if(sakup*2 == sum){
                cout << (r-l-i) << "\n";
                break;
            }
        }
    }
    return 0;
}