#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
const int M = 2e6 + 6;

char buf[1 << 23], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1 ++)
int read() {
    int s = 0, w = 1; char ch = getchar();
    while(!isdigit(ch)) { if(ch == '-') w = -1; ch = getchar(); }
    while(isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
    return s * w;
}

struct Line { 
    int l, r, id;
} q[N];
int cnt[M][2], s[N], bl[N];
long long ans[N];
int n, m, siz;

bool cmp(Line a, Line b) { 
    return bl[a.l] ^ bl[b.l] ? a.l < b.l : ((bl[a.l] & 1) ? a.r < b.r : a.r > b.r);
}

signed main() {
    n = read(), m = read(), siz = n / sqrt(m) + 1;
    for(int i = 1; i <= n; ++ i) 
        s[i] = s[i - 1] ^ (read() - 1), bl[i] = (i + 1) / siz;
    for(int i = 1; i <= m; ++ i) 
        q[i].l = read() - 1, q[i].r = read(), q[i].id = i;
    
    long long now = 0;
    sort(q + 1, q + 1 + m, cmp);
    for(int i = 1, l = 1, r = 0; i <= m; ++ i) {
        int ql = q[i].l, qr = q[i].r, id = q[i].id;
        while(l < ql) now -= -- cnt[s[l]][l & 1], ++ l;
        while(r > qr) now -= -- cnt[s[r]][r & 1], -- r;
        while(l > ql) -- l, now += cnt[s[l]][l & 1] ++;
        while(r < qr) ++ r, now += cnt[s[r]][r & 1] ++;
        ans[id] = 1ll * (qr - ql + 1) * (qr - ql) / 2 - now;
    }

    for(int i = 1; i <= m; ++ i)
        printf("%lld\n", ans[i]);
    return 0;
}