#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rel register ll
#define rec register char
#define gc getchar
//#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<23,stdin),p1==p2)?-1:*p1++)
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
char buf[1<<23],*p1=buf,*p2=buf;
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
template <typename mitsuha>
inline bool read(mitsuha &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return 0&pc(48);
  if (x<0) pc('-'),x=-x;
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  return 0;
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int yuzu=5e5;
typedef int fuko[yuzu|10];
struct node {
  int l,r,id;
  void rd(int x) {
    read(l),read(r),id=x;
  }
}qr[yuzu|10];
fuko c,cnt,lxy;
int main() {
  int i,n,q,bk;
  read(n),read(q),bk=sqrt(n);
  for (i=1;i<=n;++i) c[i]=read();
  for (i=1;i<=q;++i) qr[i].rd(i); 
  sort(qr+1,qr+q+1,[&](node a,node b){return a.l/bk^b.l/bk?a.l<b.l:a.r<b.r;});
  int nl=1,nr=0,ans=0;
  for (i=1;i<=q;++i) {
    for (;nr<qr[i].r;) !cnt[c[++nr]]++?++ans:0;
    for (;nr>qr[i].r;) !--cnt[c[nr--]]?--ans:0;
    for (;nl<qr[i].l;) !--cnt[c[nl++]]?--ans:0;
    for (;nl>qr[i].l;) !cnt[c[--nl]]++?++ans:0;
    lxy[qr[i].id]=ans;
  } 
  for (i=1;i<=q;++i) printf("%d\n",lxy[i]);
}
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define rrng(a) a.rbegin(),a.rend()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define print(x)cout<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef tuple<int,int,int> T;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
typedef vector<T> vt;

template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

int main() {
  int n,q;
  cin >>n >> q;
  vi a(n);
  vi pi(n+1,-1);
  vector<vi> p(n);
  rep(i,n){
    cin >> a[i];
  }
  rep(i,n){
    int l = pi[a[i]];
    if(l != -1)p[l].push_back(i);
    pi[a[i]] = i;
  }
  vector<vp> qs(n);
  rep(i,q){
    int l,r;
    cin >> l >> r;
    l--;r--;
    qs[l].emplace_back(r,i);
  }
  vi ans(q);
  BIT<int> d(n);
  for(int x = n-1;x>=0;x--){
    for(int y:p[x])d.add(y,1);
    for(P query : qs[x]){
      int r = query.first, i = query.second;
      ans[i] = (r-x+1) - d.sum(r);
    }
  }
  rep(i,q)cout<<ans[i]<<endl;
  return 0;
}