#include <bits/stdc++.h>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rev(i,a,b) for(int i=a;i>=b;i--)
#define Fin(file) freopen(file,"r",stdin)
#define Fout(file) freopen(file,"w",stdout)
using namespace std;
const int N=1e6+5; typedef long long ll;
ll n,B,Q,a[N],ccnt[2][N],ww[2],xsum[N]; ll cur,ans[N];
struct Query { int l,r,id; bool operator< (const Query& q) const { return l/B==q.l/B?((l/B)&1?r<q.r:r>q.r):l<q.l; } } qry[N];
void insertR(int L,int R) { cur+=(R-L+2)/2+ww[R&1]-ccnt[R&1][xsum[R]]; ccnt[R&1][xsum[R]]++; ww[R&1]++; }
void insertL(int L,int R) { cur+=(R-L+2)/2+ww[(L-1)&1]-ccnt[(L-1)&1][xsum[L-1]]; ccnt[(L-1)&1][xsum[L-1]]++; ww[(L-1)&1]++; }
void eraseR(int L,int R) { ccnt[R&1][xsum[R]]--; ww[R&1]--; cur-=(R-L+2)/2+ww[R&1]-ccnt[R&1][xsum[R]]; }
void eraseL(int L,int R) { ccnt[(L-1)&1][xsum[L-1]]--; ww[(L-1)&1]--; cur-=(R-L+2)/2+ww[(L-1)&1]-ccnt[(L-1)&1][xsum[L-1]]; }
signed main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>Q; B=sqrt(n+0.5); For(i,1,n) { cin>>a[i]; xsum[i]=xsum[i-1]^(a[i]-1); }
    For(i,1,Q) { cin>>qry[i].l>>qry[i].r; qry[i].id=i; } sort(qry+1,qry+1+Q);
    int L=1,R=0; ccnt[0][0]=1; ww[0]=1;
    For(i,1,Q){
        while(R<qry[i].r) insertR(L,++R);
        while(L>qry[i].l) insertL(--L,R);
        while(R>qry[i].r) eraseR(L,R--);
        while(L<qry[i].l) eraseL(L++,R);
        ans[qry[i].id]=cur;
    }
    For(i,1,Q) cout<<ans[i]<<'\n';
    cerr<<"Time = "<<clock()<<" ms"<<endl;
    return 0;
}

// START TYPING IF YOU DON'T KNOW WHAT TO DO