#include <iostream>
#include <stack>

int get_deg2(unsigned int a) {
    int br=0;
    while (a/2>0) {
        a/=2;
        br++;
    }
    return br;
}

int main() {
    int n, q, s, index;
    unsigned int arr[500000];
    int m[8], deg2_l[8][500000], deg2_r[8][500000];
    scanf("%d%d", &n, &q);
    for (int i=0; i<n; i++) scanf("%d", &arr[i]);

    for (int i=0; i<n; i++) m[get_deg2(arr[i])]++;

    for (int i=0; i<n; i++) {
        s = get_deg2(arr[i]);
        for (int j=0; j<8; j++) {
            if (s==j) deg2_l[j][i]=deg2_l[j][i-1]+1;
            else deg2_l[j][i]=deg2_l[j][i-1];
        }
    }

    for (int i=n-1; i>=0; i--) {
        s = get_deg2(arr[i]);
        for (int j=0; j<8; j++) {
            if (s==j) deg2_r[j][i]=deg2_r[j][i+1]+1;
            else deg2_r[j][i]=deg2_r[j][i+1];
        }
    }

    for (int i=0; i<q; i++) {
        int l, r, maximum=0;
        scanf("%d%d", &l, &r);
        l--;
        r--;
        for (int j=0; j<8; j++) {
            if (m[j] - (deg2_r[j][r] + deg2_l[j][l])+1 > maximum)
                maximum = m[j] - (deg2_r[j][r] + deg2_l[j][l])+1;
        }
        printf("%d\n", maximum);
    }
    return 0;
}