#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


// Manages linearly independent set in \F_2^n of max weight.
//   S  should be an integral type and support taking a bit and addition (^).
//   T  should support addition and comparison.
//   invariant:  ss[i] = 0  ||  2^i <= ss[i] < 2^(i+1)
template <class S, class T> struct Basis {
  int n;
  vector<S> ss;
  vector<T> ts;
  T total;
  Basis(int n_) : n(n_), ss(n, 0), ts(n, 0), total(0) {}
  void add(S s, T t) {
    total += t;
    for (int i = n; --i >= 0; ) if (s >> i & 1) {
      if (ss[i]) {
        if (ts[i] < t) {
          swap(ss[i], s);
          swap(ts[i], t);
        }
        s ^= ss[i];
      } else {
        ss[i] = s;
        ts[i] = t;
        return;
      }
    }
    total -= t;
  }
};

////////////////////////////////////////////////////////////////////////////////


template <class T> void bAdd(vector<T> &bit, int pos, const T &val) {
  const int bitN = bit.size();
  for (int x = pos; x < bitN; x |= x + 1) bit[x] += val;
}
template <class T> T bSum(const vector<T> &bit, int pos) {
  T ret = 0;
  for (int x = pos; x > 0; x &= x - 1) ret += bit[x - 1];
  return ret;
}
template <class T> T bSum(const vector<T> &bit, int pos0, int pos1) {
  return bSum(bit, pos1) - bSum(bit, pos0);
}

// min pos s.t. pred(sum of [0, pos))
//   assume pred(sum of [0, pos)) is non-decreasing
template <class T, class Pred>
int bBinarySearch(const vector<T> &bit, Pred pred) {
  if (pred(T(0))) return 0;
  const int bitLen = bit.size();
  int pos = 0;
  T sum = 0;
  for (int e = 31 - __builtin_clz(bitLen); e >= 0; --e) {
    const int x = (pos | 1 << e) - 1;
    if (x < bitLen && !pred(sum + bit[x])) {
      pos |= 1 << e;
      sum += bit[x];
    }
  }
  return pos + 1;
}


constexpr int E = 30;

int N;
vector<vector<pair<pair<int, int>, Int>>> ess;

void init(int N_, int Q, vector<int> A) {
  N = N_;
// cerr<<"[init] "<<N<<" "<<Q<<" "<<A<<endl;
  // vector<vector<pair<int, int>>> pss(N);
  vector<vector<int>> lss0(N + 2), lss1(N + 2);
  {
    Basis<int, Int> basis(E);
    map<int, int> app;
    vector<int> bit(N, 0);
    for (int i = N; --i >= 0; ) {
      basis.add(A[i], -i);
// cerr<<"ss = "<<basis.ss<<", ts = "<<basis.ts<<endl;
      {
        auto it = app.find(A[i]);
        if (it != app.end()) {
          bAdd(bit, it->second, -1);
        }
        app[A[i]] = i;
        bAdd(bit, i, +1);
      }
      int jsLen = 0;
      int js[E + 1];
      js[jsLen++] = i;
      for (int e = 0; e < E; ++e) if (basis.ss[e]) js[jsLen++] = -basis.ts[e];
      sort(js, js + jsLen);
      js[jsLen] = N;
// cerr<<"js = ";pv(js,js+(jsLen+1));
      for (int d = 0; d < jsLen; ++d) {
        // js[d] < r <= js[d + 1] ==> dim = d
        if (js[d] < js[d + 1] && 1 << d <= (int)app.size()) {
          const int pos = bBinarySearch(bit, [&](int sum) -> bool {
            return (sum >= 1 << d);
          });
          // pos <= r <= js[d + 1]
          if (pos <= js[d + 1]) {
            // pss[i].emplace_back(pos, js[d + 1] + 1);
            lss0[pos].push_back(i);
            lss1[js[d + 1] + 1].push_back(i);
          }
        }
      }
    }
  }
// cerr<<"pss = "<<pss<<endl;
  ess.assign(N, {});
  /*
  for (int i = 0; i < N; ++i) {
    for (int x = N - 1 - i; x < N; x |= x + 1) {
      for (const auto &p : pss[i]) {
        ess[x].emplace_back(make_pair(p.first, +1), 0LL);
        ess[x].emplace_back(make_pair(p.second, -1), 0LL);
      }
    }
  }
  */
  for (int r = 0; r <= N + 1; ++r) {
    for (const int l : lss0[r]) for (int x = N - 1 - l; x < N; x |= x + 1) ess[x].emplace_back(make_pair(r, +1), 0LL);
    for (const int l : lss1[r]) for (int x = N - 1 - l; x < N; x |= x + 1) ess[x].emplace_back(make_pair(r, -1), 0LL);
  }
  for (int x = 0; x < N; ++x) {
    auto &es = ess[x];
    // sort(es.begin(), es.end());
    for (int k = 1; k < (int)es.size(); ++k) {
      es[k].first.second += es[k - 1].first.second;
      es[k].second = es[k - 1].second + (Int)es[k - 1].first.second * (es[k].first.first - es[k - 1].first.first);
    }
// cerr<<"ess["<<x<<"] = "<<es<<endl;
  }
}

Int solve(int L, int R) {
  ++R;
  Int ans = 0;
  // L <= l <=> N - 1 - l <= N - 1 - L
  for (int x = (N - 1 - L) + 1; x; x &= x - 1) {
    const auto &es = ess[x - 1];
    auto it = lower_bound(es.begin(), es.end(), make_pair(make_pair(R + 1, -1), -1LL));
    if (it != es.begin()) {
      --it;
      ans += it->second + (Int)it->first.second * (R + 1 - it->first.first);
    }
  }
// cerr<<"[solve] "<<L<<" "<<R<<" = "<<ans<<endl;
  return ans;
}