#include<bits/stdc++.h>
using namespace std;
const int MAXBIT=64;
struct BitRank
{
  // block: bit 列を管理, count: block ごとに立っている 1 の数を管理
  vector<unsigned long> block;
  vector<int> count;
  BitRank(){}
  void resize(int num) {
    block.resize((num + 1) / MAXBIT + 1, 0);
    count.resize((int)block.size(), 0);
  }
  // i ビット目を val(0,1) にセット
  inline void set(int i, unsigned long val) {
    block[i/MAXBIT] |= (val << (i % MAXBIT));
  }
  void build() {
    for(int i = 1; i < (int)block.size(); i++){
      count[i] = count[i-1] + __builtin_popcountll(block[i-1]);
    }
  }
  // [0, i) ビットの 1 の数
  inline int rank1(int i) {
    return count[i/MAXBIT] + ((i % MAXBIT) ? __builtin_popcountll(block[i/MAXBIT] << (MAXBIT-i%MAXBIT)) : 0);
  }
  // [j, i) ビットの 1 の数
  inline int rank1(int i, int j) {
    return rank1(j) - rank1(i);
  }
  // [0, i) ビットの 0 の数
  inline int rank0(int i) {
    return i - rank1(i);
  }
  // [j, i) ビットの 0 の数
  inline int rank0(int i, int j) {
    return rank0(j) - rank0(i);
  }
};
class WaveletMatrix
{
  private:
  int height;
  vector<BitRank> B;
  vector<int> pos;
  public:
  WaveletMatrix(){}
  WaveletMatrix(vector<int>& vec) :
  WaveletMatrix(vec, *max_element(vec.begin(), vec.end()) + 1) {}
  // sigma:文字の種類数
  WaveletMatrix(vector<int>& vec, int sigma){
    init(vec, sigma);
  }
  void init(vector<int>& vec, int sigma){
    height = (sigma == 1) ? 1 : (MAXBIT - __builtin_clzll(sigma));
    B.resize(height), pos.resize(height);
    for(int i = 0; i < height; i++){
      B[i].resize((int)vec.size());
      for(int j = 0; j < (int)vec.size(); j++) {
        B[i].set(j, get(vec[j], height - i - 1));
      }
      B[i].build();
      auto it = stable_partition(vec.begin(), vec.end(), [&](int c) {
        return !get(c, height - i - 1);
      });
      pos[i] = it - vec.begin();
    }
  }
  // val の i ビット目の値を返す(0,1)
  inline int get(int val, int i) {
    return val >> i & 1;
  }
  // [l, r) の間に現れる値 val の数
  int rank(int val, int l, int r) {
    return rank(val, r) - rank(val, l);
  }
  // [0, i) の間に現れる値 val の数
  int rank(int val, int i) {
    int p = 0;
    for(int j = 0; j < height; j++){
      if(get(val, height - j - 1)){
        p = pos[j] + B[j].rank1(p);
        i = pos[j] + B[j].rank1(i);
      }else{
        p = B[j].rank0(p);
        i = B[j].rank0(i);
      }
    }
    return i - p;
  }
  // [l, r) の k(1,2,3...) 番目に小さい値を返す
  int quantile(int k, int l, int r) {
    int res = 0;
    for(int i = 0; i < height; i++){
      int j = B[i].rank0(l, r);
      if(j >= k){
        l = B[i].rank0(l);
        r = B[i].rank0(r);
      }else{
        l = pos[i] + B[i].rank1(l);
        r = pos[i] + B[i].rank1(r);
        k -= j;
        res |= (1 << (height - i - 1));
      }
    }
    return res;
  }
  // [l,r) で値が [a,b) 内に含まれる数を返す
  int rangefreq(int l, int r, int a, int b) {
    return rangefreq(l, r, a, b, 0, 1 << height, 0);
  }
  int rangefreq(int i, int j, int a, int b, int l, int r, int x) {
    if(r <= a || b <= l) return 0;
    int mid = (l + r) >> 1;
    if(a <= l && r <= b){
      return j - i;
    }else{
      return rangefreq(B[x].rank0(i),B[x].rank0(j),a,b,l,mid,x+1)
      +rangefreq(pos[x]+B[x].rank1(i),pos[x]+B[x].rank1(j),a,b,mid,r,x+1);
    }
  }
};
#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;}
  WaveletMatrix wm;
  wm.init(direction,N);
  while(Q--){int l=IN()-1,r=IN();OUT(wm.rangefreq(l,r,r,N+1));}
}

Measured memory_bytes: 12816