//g++ t.cpp -o t && t < p.txt
//d>p.txt&&t<p.txt&&t2<p.txt

#include <iostream> // プログラムの耳と口
#include <vector> // 超有能配列秘書
#include <algorithm> // みんな大好きソートと二分探索
#include <queue> // きゅーちゃん、だいすき
#include <string> // to_string
#include <functional> // 関数を変数に入れる子
#include <set> // 値の取得・挿入・削除を高速に
#include <map> // setの妹 これまた優秀
#include <random> // 乱択さん
#include <ctime>

#define DB cerr<<"D"<<endl
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";};
using P=pair<ll,ll>;
const ll M = 1e9+7;
ll mod_pow(ll x, ll a) { ll an = 1; while(a > 0) { if (a&1) an = an * x % M; x = x * x % M; a >>= 1;} return an;}
void add(ll& x, ll y) {x+=y; x%=M;}; void mul(ll& x, ll y) {x*=y; x%=M;}; template<typename T, typename U> void chmax(T& x, U y) {if (x<y) x=y;}; template<typename T, typename U> void chmin(T& x, U y) {if (x>y) x=y;}
bool vaild(int x, int y, int hh, int ww){return 0<=x&&x<hh&&0<=y&&y<ww;}
int keta(ll a) {int res=0; while(a>0) res+=a%10, a/=10; return res;}

template <typename T>
struct seg_Lp {
  // 区間更新、一点取得
  using F = function<T(T,T)>;
  const F f,g; const T ft; vector<T> lazy; int m, n, n2;
  seg_Lp(int _m, F _f, T _ft) : m(_m), f(_f), ft(_ft) {
    n=1; while(m>n) n<<=1;
    n2=2*n; lazy.resize(n2);
    for(int i=1;i<n2;i++) lazy[i]=ft;
  }

  // 増加
  void update(int k, int a, int b, int v, int l, int r) {
    if (a <= l && r <= b) {lazy[k] = f(lazy[k],v); return;}
    else if (a >= r || b <= l) return;
    else {
      update(2*k, a, b, v, l, (l+r)/2);
      update(2*k+1, a, b, v, (l+r)/2, r);
    }
  }

  // 増加（使用用）
  void update(int a, int b, int v) {
    update(1, a, b, v, 0, n);
  }

  // 合計
  T sum(int k) {
    //int fir = sum[k];
    k+=n;
    int ins = lazy[k];
    while(k>0) {
      k = k / 2;
      ins = f(ins,lazy[k]);
    }
    return ins; 
  }
  void print() {
    for(int i=1,j=0;i<n2;i++) {
      if (i+1 > (1<<j)) {cout<<endl; j++;}
      cout<<lazy[i]<<" ";
    } cout<<endl;
  }
};

int main() {
  int n,q; cin>>n>>q;
  int c[n];
  for(int i=0;i<n;i++) {cin>>c[i]; c[i]--;}
  using ppi = pair<pair<int,int>,int>;
  ppi p[q];
  for(int i=0;i<q;i++) {
    cin>>p[i].first.second>>p[i].first.first;
    p[i].first.second--;
    p[i].first.first--;
    p[i].second=i;
  }
  sort(p,p+q);
  /*
  for(int i=0;i<q;i++) {
    cout<<p[i].first.first<<" "<<p[i].first.second<<" "<<p[i].second<<endl;
  }*/

  seg_Lp<int> sg(n, [](int x, int y){return x+y;}, 0);

  int bf[n]; fill(bf,bf+n,-1);
  int an[q]; fill(an,an+q,-1);
  int ii = 0;
  for(int i=0;i<n;i++) {
    int cc = c[i];
    if (bf[cc] != -1) {
      sg.update(0,bf[cc]+1,1);
    }
    bf[cc] = i;
    while(ii < q && p[ii].first.first == i) {
      //cout << ii << " " << p[ii].first.first <<" "<< p[ii].first.second <<" "<< sg.sum(p[ii].first.second)<<endl;
      an[p[ii].second] = p[ii].first.first - p[ii].first.second + 1 - sg.sum(p[ii].first.second);
      ii++;
    }
    //cout<<i<<" "<<ii<<" "<<cc<<" "<<p[ii].first.first<<endl;
    //sg.print();
  }
  for(int i=0;i<q;i++) {
    cout<<an[i]<<endl;
  }
}
// ・配列の大きさok？　・priority_queueはgreater？　・debug消した？
// ・落ち着いて。提出まで4分待ってね……WJ……1/10……2/10……

// Thank you for making problems and running the contest


Measured memory_bytes: 19516