#include<iostream>
#define MAX 2
using namespace std;
void unos(unsigned long int a[], unsigned int n)
{
    for(int i=0;i<n;i++)
        cin>>a[i];
}
void unosmatrice(int a[][MAX], int q)
{
    for(int i=0;i<q;i++)
        for(int j=0;j<2;j++)
            cin>>a[i][j];
}
int hormutacija(unsigned long int a[], int l, int r)
{
    for(int i=l;i<=r;i++)
    {
        int br=0;
        if(a[i]&a[i+1]>a[i]^a[i+1])
            br++;
        if(a[i]&a[i]>a[i]^a[i])
            br++;
        return br;
    }
}
int main()
{
    unsigned int n,q,l,r;
    cin>>n>>q;
    unsigned long int a[n];
    int b[q][MAX];
    unos(a,n);
    unosmatrice(b,q);
    for(int i=0;i<q;i++)
    {
        int l=b[i][0];
        int r=b[i][1];
        cout<<hormutacija(a,l,r)<<endl;;
    }
    return 0;
}