#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,bmi,bmi2,lzcnt")
#endif
#include<bits/stdc++.h>
using namespace std;

template <class T> struct wavelet_matrix {
  using size_type = uint32_t;
  struct bit_vector {
    static constexpr size_type wsize = 64;
    static size_type rank64(uint64_t x, size_type i) {
      return __builtin_popcountll(x&((1ull<<(i%wsize))-1));
    }
#pragma pack(4)
    struct block_t {
      uint64_t bit;
      size_type sum;
    };
#pragma pack()
    size_type n, zeros;
    vector<block_t> block;
    bit_vector(size_type _n = 0) : n(_n), block(n / wsize + 1) {}
    int operator[](size_type i) const {
      return block[i / wsize].bit >> i % wsize & 1;
    }
    void set(size_type i) { block[i / wsize].bit |= (uint64_t)1 << i % wsize; }
    void build() {
      for (size_type j = 0; j < n / wsize; ++j)
        block[j + 1].sum = block[j].sum + __builtin_popcountll(block[j].bit);
      zeros = rank0(n);
    }
    size_type rank0(size_type i) const { return i - rank1(i); }
    size_type rank1(size_type i) const {
      auto&& e = block[i / wsize];
      return e.sum + rank64(e.bit, i % wsize);
    }
  };
  size_type n, lg;
  vector<T> a;
  vector<bit_vector> bv;
  wavelet_matrix(size_type _n = 0) : n(_n), a(n) {}
  T& operator[](size_type i) { return a[i]; }
  void build() {
    lg = __lg(max<T>(*max_element(begin(a), end(a)), 1)) + 1;
    bv.assign(lg, n);
    vector<T> cur = a, nxt(n);
    for (auto h = lg; h--; ) {
      for (size_type i = 0; i < n; ++i) if (cur[i] >> h & 1) bv[h].set(i);
      bv[h].build();
      array it{begin(nxt), begin(nxt) + bv[h].zeros};
      for (size_type i = 0; i < n; ++i) *it[bv[h][i]]++ = cur[i];
      swap(cur, nxt);
    }
  }
  T kth(size_type l, size_type r, size_type k) const {
    T res = 0;
    for (auto h = lg; h--; ) {
      auto l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
      if (k < r0 - l0) l = l0, r = r0;
      else {
        k -= r0 - l0;
        res |= (T)1 << h;
        l += bv[h].zeros - l0;
        r += bv[h].zeros - r0;
      }
    }
    return res;
  }
  size_type count(size_type l, size_type r, T ub) const {
    if (ub >= (T)1 << lg) return r - l;
    size_type res = 0;
    for (auto h = lg; h--; ) {
      auto l0 = bv[h].rank0(l), r0 = bv[h].rank0(r);
      if (~ub >> h & 1) l = l0, r = r0;
      else {
        res += r0 - l0;
        l += bv[h].zeros - l0;
        r += bv[h].zeros - r0;
      }
    }
    return res;
  }
  size_type count(size_type l, size_type r, T lb, T ub) const {
    return count(l, r, ub) - count(l, r, lb);
  }
};
#define rep(i,N) for(int i=0;i<(int)N;i++)
static inline void PUT(char c)
{
  static char buf[1<<15],*ptr=buf;
  if(ptr==buf+strlen(buf)||c==0){fwrite(buf,1,ptr-buf,stdout),ptr=buf;}*ptr++=c;
}
static inline int IN(void)
{
  int x=0,f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
static inline void OUT(int a)
{
  if(a<0)PUT('-'),a=-a;
  int d[40],i=0;do{d[i++]=a%10;}while(a/=10);
  while(i--){PUT(d[i]+48);}PUT('\n');
}
int main()
{
  int N=IN(),Q=IN(),mn=N,mx=0,C[N],temp[N];
  vector<int>direction(N);
  rep(i,N){C[i]=IN();mn=mn<C[i]?mn:C[i];mx=mx>C[i]?mx:C[i];temp[i]=N;}
  rep(i,N){direction[N-1-i]=temp[C[N-1-i]-1];temp[C[N-1-i]-1]=N-1-i;}
  wavelet_matrix<int> wm(N);
  rep(i,N){wm[N-1-i]=exchange(direction[N-1-i],N-1-i);}
  wm.build();
  while(Q--){int l=IN()-1,r=IN();OUT(r-l-wm.count(l,r,r));}
}

Measured memory_bytes: 16616