#include<cmath>
#include<queue>
#include<stack>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>

using namespace std;

typedef long long ll ;
const int N = 1e6 + 5 ;

int rd()
{
	int res = 0 , f = 1 ;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')f = -1 ; ch = getchar() ;}
	while(ch >= '0' && ch <= '9')res = (res << 1) + (res << 3) + (ch ^ 48) , ch = getchar() ;
	return res * f ;
}

int n , q , sq ;

struct Q
{
	int l , r , p ;
	Q(){}
	Q(int a , int b , int c):l(a),r(b),p(c){};
	bool operator < (Q q) const
	{
		if(l / sq != q.l / sq) return l < q.l ;
		return r < q.r ;
	}
	~Q(){}
}que[N] ;

int a[N] , pre[N] ;

ll sum , ans[N] ;
int cnt[2][N] , l = 1 , r ;
int C2(int n){return n * (n - 1) / 2 ;}

void del(int p)
{
	sum -= C2(cnt[p & 1][pre[p]]--) ;
	sum += C2(cnt[p & 1][pre[p]]) ;
}

void add(int p)
{
	sum -= C2(cnt[p & 1][pre[p]]++) ;
	sum += C2(cnt[p & 1][pre[p]]) ;
}

int query(int ql , int qr)
{
	while(l > ql) add(--l) ;
	while(l < ql) del(l++) ;
	while(r < qr) add(++r) ;
	while(r > qr) del(r--) ;
	return sum ;
}

int main()
{
	n = rd() ; q = rd() ; sq = sqrt(n) ;
//	for(int i = 1 ; i <= n ; i++)
//		a[i] = rd() ;
	for(int i = 1 ; i <= n ; i++)
		pre[i] = pre[i - 1] ^ (rd() - 1) ;

	for(int i = 1 ; i <= q ; i++)
	{
		int a = rd() - 1 , b = rd() ;
		que[i] = Q(a , b , i) ;
	}
//	for(int i = 1 ; i <= q ; i++)
//		que[i] = Q(rd() - 1 , rd() , i) ;
	sort(que + 1 , que + 1 + q) ;

	for(int i = 1 ; i <= q ; i++)
//		cout << que[i].l << ' ' << que[i].r << ' ' << que[i].p << '\n' ,
		ans[que[i].p] = C2(que[i].r - que[i].l + 1) - query(que[i].l , que[i].r) ;
	for(int i = 1 ; i <= q ; i++)
		cout << ans[i] << '\n' ;
	return 0 ;
}