#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()
#define STRINGIFY(n) #n
#define TOSTRING(n) STRINGIFY(n)
#define PREFIX "#" TOSTRING(__LINE__) "| "
#define debug(x) \
{ \
  std::cout << PREFIX << #x << " = " << x << std::endl; \
}

std::ostream& output_indent(std::ostream& os, int ind) {
  for(int i = 0; i < ind; i++) os << " ";
  return os;
}

template<class S, class T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p);
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v);

template<class S, class T> std::ostream& operator<<(std::ostream& os, const std::pair<S, T>& p) {
  return (os << "(" << p.first << ", " << p.second << ")");
}
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& v) {
  os << "[";
  for(int i = 0;i < v.size();i++) os << v[i] << ", ";
  return (os << "]");
}

template<class T>
static inline std::vector<T> ndvec(size_t&& n, T val) { return std::vector<T>(n, std::forward<T>(val)); }
template<class... Tail>
static inline auto ndvec(size_t&& n, Tail&&... tail) {
  return std::vector<decltype(ndvec(std::forward<Tail>(tail)...))>(n, ndvec(std::forward<Tail>(tail)...));
}
template<class Cond> struct chain {
  Cond cond; chain(Cond cond) : cond(cond) {}
  template<class T> bool operator()(T& a, const T& b) const { if(cond(a, b)) { a = b; return true; } return false; }
};
template<class Cond> chain<Cond> make_chain(Cond cond) { return chain<Cond>(cond); }

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define rev(i,s,e) for(i64 (i) = (e); (i)-- > (s);)
#define all(x) x.begin(),x.end()

struct Mo {
  vector<int> left, right, order;
  vector<bool> v;
  

  const i64 width;
  i64 nl, nr, ptr;

  vector<int> a;
  vector<int> cnt;
  i64 ans;

  Mo(i64 n, vector<int> a) : v(n), width(10), nl(0), nr(0), ptr(0), a(a), cnt(505050), ans(0) {}

  void add_query(i64 l, i64 r) {
    left.push_back(l);
    right.push_back(r);
  }

  void build() {
    order.resize(left.size());
    for(i64 i = 0;i < left.size();i++) order[i] = i;
    sort(begin(order), end(order), [&](i64 a, i64 b) {
        if(left[a] >> width != left[b] >> width) return left[a] < left[b];
        else return right[a] < right[b];
        });
  }


  void add(i64 idx) {
    if(cnt[a[idx]]++ == 0) ans++;
  }
  void del(i64 idx) {
    if(--cnt[a[idx]] == 0) ans--;
  }

  inline void distribute(i64 idx) {
    v[idx].flip();
    if(v[idx]) add(idx);
    else del(idx);
  }

  i64 process() {
    if(ptr == order.size()) return -1;
    const auto id = order[ptr];
    while(nl > left[id]) distribute(--nl);
    while(nr < right[id]) distribute(nr++);
    while(nl < left[id]) distribute(nl++);
    while(nr > right[id]) distribute(--nr);
    return order[ptr++];
  }
};

#include <unistd.h>

namespace niu {

  struct fastin {
    static const int bufsize = 1 << 24;
    char buf[bufsize];
    char* iter;
    fastin() {
      iter = buf;
      for(int t = 0, k; (k = read(STDIN_FILENO, buf + t, sizeof(buf)) - t) > 0; t += k);
    }
    fastin& operator>>(int& num) {
      num = 0;
      bool neg = false;
      while(*iter < '+') iter++;
      if(*iter == '-') { neg = true; iter++; }
      else if(*iter == '+') iter++;
      while(*iter >= '0') num = 10 * num + *(iter++) - '0';
      if(neg) num = -num;
      return *this;
    } 
  } fin;
  struct fastout {
    static const int bufsize = 1 << 22;
    char buf[bufsize];
    char* iter;
    fastout() {
      iter = buf;
    }
    ~fastout() {
      for(int t = 0, k; (k = write(STDOUT_FILENO, buf + t, iter - buf - t)) > 0; t += k);
    }
    fastout& operator<<(int num) {
      static char tmp[20];
      if(num == 0) {
        *(iter++) = '0';
        return *this;
      }
      if(num < 0) {
        *(iter++) = '-';
        num = -num;
      }
      int i = 0;
      while(num) {
        tmp[i++] = num % 10;
        num /= 10;
      }
      while(i--) {
        *(iter++) = tmp[i] + '0';
      }
      return *this;
    }
    fastout& operator<<(char c) {
      *(iter++) = c;
      return *this;
    }
  } fout;
}

int main() {
  int N, Q;
  niu::fin >> N >> Q;
  vector<int> c(N);
  rep(i,0,N) niu::fin >> c[i];
  Mo mo(N, std::move(c));
  mo.left.reserve(Q);
  mo.right.reserve(Q);
  rep(i,0,Q) {
    int l, r;
    niu::fin >> l >> r;
    mo.add_query(l - 1, r);
  }
  mo.build();
  vector<int> ans(Q);
  i64 res = 0;
  while((res = mo.process()) != -1) {
    ans[res] = mo.ans;
  }
  rep(i,0,Q) {
    niu::fout << ans[i] << '\n';
  }
}


Measured memory_bytes: 27736