666

#include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = 2000010;

struct P{
int l,r,id;
}qry[N];

int be[N],L[N],R[N];

bool cmp(P a,P b){
if(be[a.l]!=be[b.l]) return be[a.l]<be[b.l];
return be[a.r]<be[b.r];
}

int a[N],s[N];
int cnt[2][M];
long long sum;
void add(int x){
sum+=cnt[x&1][s[x]];
cnt[x&1][s[x]]++;
}
void del(int x){
cnt[x&1][s[x]]--;
sum-=cnt[x&1][s[x]];
}

long long ans[N];

int main(){
int n;cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i]=s[i-1]^(a[i]-1);
}
int q;cin>>q;
for(int i=0;i<q;i++){
cin>>qry[i].l>>qry[i].r;
qry[i].l--;
qry[i].id=i;
}

int block=sqrt(n);
int tot=(n+block-1)/block;
for(int i=1;i<=tot;i++){
    L[i]=(i-1)*block+1;
    R[i]=min(n,i*block);
    for(int j=L[i];j<=R[i];j++) be[j]=i;
}
sort(qry,qry+q,cmp);

long long l=1,r=0;
for(int i=0;i<q;i++){
    P Q=qry[i];
    while(l>Q.l) add(--l);
    while(r<Q.r) add(++r);
    while(l<Q.l) del(l++);
    while(r>Q.r) del(r--);

    long long res=(r-l+1)*(r-l)/2-sum;
    ans[Q.id]=res;
}

for(int i=0;i<q;i++) cout<<ans[i]<<endl;

}