//
// Created by codicon on 3/13/2023 at 11:21 AM.
//

// O(N sqrt(Q))

/*
 * First, for a given set of piles, S, who wins?
 *
 * Observation:
 *      1 pile:
 *           First player wins
 *      2 piles:
 *           Let's say that player A performs an operation and now there is only 1 pile left.
 *           Then, by our solution for 1 pile, player B wins.
 *
 *           Denote the piles where we remove 1 stone from each pile as S'.
 *           Thus, the winner of the game is the winner of nim on S'.
 *
 *           This is because either:
 *               The game of nim is played to completion (all piles have 1 stone now).
 *               Then, the loser removes the final stone from some pile. Now there is 1 pile left.
 *               or
 *               The loser completely removes a pile before the game of nim is completed.
 *               In this case, there is also 1 pile left.
 *      3 piles:
 *           WLOG, say the piles have stones: a < b < c.
 *           Then, player 1 can simply remove stones from c until there are b-a left.
 *           Then, they merge those b-a stones into a. Now the piles are (b, b).
 *
 *           Thus, player 1 wins since the game has reduced to the 2 pile case and
 *           player 1 wins nim on (b-1, b-1).
 *      4 piles:
 *           Again, if player A removes a pile, the game reduces to the 3 pile case and
 *           the player A loses.
 *
 *           Thus, winner of the game on S' is the winner.
 *
 * Proof of Full Strategy via Induction:
 *      It seems like player 1 wins when there are an odd number of piles and
 *      if there are an even number of piles, the winner is the winner of nim on S'.
 *
 *      Base Case:
 *          For n = 1 the statement is true.
 *
 *      Inductive Hypothesis:
 *          Let n >= 1 such that the statement is true for n.
 *
 *      Inductive Step:
 *          Let's prove the statement for n+1
 *
 *          If n is odd:
 *              No player wants to remove any pile and thus the winner is the winner of nim on S'.
 *
 *          If n is even:
 *              Let's prove that it is always possible for the first player to
 *              remove stones from some pile and then merge the remaining stones into
 *              some other pile such that they would win nim on S'.
 *
 *              For player 1 to win nim on S', the xor-sum after they move must be 0.
 *
 *              Consider how the operations affect the pile sizes and thus xor-sum on S':
 *              We have to pick some pile X (has X+1 stones in S). Then, remove X and add
 *              up to X stones to some pile A (has A+1 stones in S). We need the xor-sum = 0.
 *              Thus, we must change A to A xor (S' xor X). Here S' xor X denotes xor-sum(S') xor X.
 *
 *              This means we can do so iff A <= (A xor (S' xor X)) <= A + X.
 *
 *              Realize that xoring A by (S' xor X) can increase A by at most (S' xor X).
 *              Accordingly, let's start by finding a pile X such that X >= S' xor X.
 *              Thus, we will at least be able to ensure:
 *              A xor (S' xor X) <= A + X.
 *
 *                  Let sum(i), be the sum of the ith bits of all piles in S'.
 *
 *                  Then, iterate i from the most significant bit to the least.
 *                  If sum(i) is even, continue.
 *                  Otherwise, sum(i) is odd, so find any pile X such that
 *                  the ith bit is on.
 *
 *                  This means X >= S' xor X since they have the same bits in positions > i
 *                  and X has the ith bit on whilst S' xor X does not.
 *
 *                  If we reach i = 1 and sum(i) is even, then that just means
 *                  X = S' xor X for any X, so X >= S' xor X.
 *
 *              Now, to satisfy the entire condition: A <= A xor (S' xor X) <= A + X,
 *              we need to satisfy A <= A xor (S' xor X).
 *              Now, the cool part is that since n is even, we can find a pile A
 *              that satisfies the condition for any X!
 *
 *                  Let i be the most significant on bit in (S' xor X)
 *                  Since n is even, there must exist at least one pile A such that
 *                  the ith bit is off.
 *                  Thus, A < A xor (S' xor X), so A <= A xor (S' xor X).
 *
 *                  If there is no most significant on bit in (S' xor X), then (S' xor X) = 0.
 *                  Thus, A xor (S' xor X) = A, so A <= A xor (S' xor X).
 *
 *              Thus, we've proved that if n is even, we can find pile X and A in S' such that
 *              we can remove some stones from pile X and add the remaining to A such that xor-sum(S') = 0.
 *
 * Full Solution:
 *      To actually answer queries, we just need to use Mo's algorithm to maintain:
 *          1. The number of odd length subarrays
 *          2. The number of even length subarrays with xor-sum != 0.
 */


#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e5, MAXXOR = 1.1e6, SQRTN = 300;

int n, q;
int a[MAXN + 1];
long long ans[MAXN];

int pxor[MAXN + 1];
int pxor_cnt[2][MAXXOR + 1];

struct query {
    int i, l, r;

    bool operator < (const query other) const {
        return make_pair(i/SQRTN, r) < make_pair(other.l/SQRTN, other.r);
    }
};

vector<query> queries;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < q; i++) {
        int l, r; cin >> l >> r;

        queries.push_back({i, l, r});
    }

    for (int i = 1; i <= n; i++) {
        pxor[i] = (a[i]-1) ^ pxor[i-1];
    }

    // Mo's
    sort(queries.begin(), queries.end());

    int l = 1, r = 0;
    pxor_cnt[0][0]++;
    long long cans = 0;

    auto add = [&](int idx, bool left) {
        cans += (r-l+1)/2 - pxor_cnt[idx-left&1][pxor[idx-left]]++; // even length, diff xor
        cans += (r-l+2)/2; // odd length
    };
    auto remove = [&](int idx, bool left) {
        cans -= (r-l+1)/2 - --pxor_cnt[idx-left&1][pxor[idx-left]]; // even length, diff xor
        cans -= (r-l+2)/2; // odd length
    };

    for (auto q: queries) {
        while (q.l < l) {
            l--;
            add(l, true);
        }
        while (q.r > r) {
            r++;
            add(r, false);
        }
        while (q.l > l) {
            remove(l, true);
            l++;
        }
        while (q.r < r) {
            remove(r, false);
            r--;
        }

        ans[q.i] = cans;
    }

    for (int i = 0; i < q; i++) {
        cout << ans[i] << '\n';
    }
}