// https://www.youtube.com/watch?v=wthasN45KuY
// You said I’d fly away
// But my walls have kept me down
// Now I’m lost and I’m afraid
// And I’m close to hit the ground
// 
// You said I’d fly away
// You said I’d fly anywhere
// But I keep on Falling

#ifndef ONLINE_JUDGE
#include "templates/debug.hpp"
#else
#define debug(...)
#endif

#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using u64 = uint64_t;

#define int i64
constexpr int INF = 1e9 + 7;
constexpr int B = 333;
struct Query {
    int l, r, id;
    bool operator<(const Query& o) const {
        return (l / B == o.l / B) ? (r < o.r) ^ (l / B & 1) : (l < o.l);
    }
};
void solve() {
    int n, q; cin >> n >> q;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> pres(n + 1, 0);
    for (int i = 1; i <= n; i++) pres[i] = pres[i - 1] ^ (a[i] - 1);
    constexpr int M = 1 << 20;
    vector<int> cnto(M), cnte(M);
    vector<int> ans(q);
    vector<Query> qry(q);
    for (int qi = 0; qi < q; qi++) {
        int l, r; cin >> l >> r;
        l--; qry[qi] = {l, r, qi};
    }
    int l = 0, r = 0;
    cnte[0]++;
    int now = 0;
    sort(qry.begin(), qry.end());
    int ocnt = 0, ecnt = 1;
    auto add = [&](int i) {
        if (i % 2) now += cnto[pres[i]]++, ocnt++;
        else now += cnte[pres[i]]++, ecnt++;
    };
    auto del = [&](int i) {
        if (i % 2) now -= --cnto[pres[i]], ocnt--;
        else now -= --cnte[pres[i]], ecnt--;
    };
    for (auto [ql, qr, id]: qry) {
        while (l > ql) add(--l);
        while (r < qr) add(++r);
        while (l < ql) del(l++);
        while (r > qr) del(r--);
        ans[id] = (r - l) * (r - l + 1) / 2 - now;
        debug(ql, qr, ocnt, ecnt, now);
    }
    for (int x: ans) cout << x << '\n';
}
#undef int

// Make bold hypotheses and verify carefully
int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}