Mali Đurica je veliki obožavatelj knjiga i čvrsto je rešio da pročita što više knjiga u narednih godinu dana. Prvi, jelte, logičan korak je da ode u biblioteku i tamo potraži štivo za čitanje, što je Đurica i uradio. Radi pojednostavljenja, biblioteku ćemo zamisliti kao niz knjiga. Đurica smatra da će čitanje biti zanimljivije ako čita knjige različitih autora. Shodno tome, prva stvar koju je Đurica zaključio da mu je neophodna jeste da prebroji koliko različitih autora je učestvovalo u pisanju datog podniza uzastopnih knjiga.

Tu stupate vi. Baš vas je zamolio Đurica da mu pomognete i date odgovor na dato pitanje. Jedna olakšavajuća okolnost je to što za svaku knjigu važi da je pisao isključivo jedan autor. Umesto imena autora knjige, Đurica će vam dati jedinstveni broj autora, koji je u stvari broj iz intervala [1, 100 000]. Svaki autor ima tačno jedan jedinstveni broj, i svaki jedinstven broj odgovara tačno jednom autoru.

Ulaz.

(Ulazni podaci se učitavaju iz datoteke knjige.in.) U prvom redu nalaze se celi brojevi n (1 ≤ n ≤ 100:000) i K (1 ≤ K ≤ 100:000). U narednom redu se učitava n celih brojeva iz intervala [1, 100 000] koji redom predstavljaju jedinstvene brojeve autora knjiga datog niza. Potom se u K redova učitavaju redom indeksi idxs_i i idxe_i (idxs_i ≤ idxe_i, 1 ≤ i ≤ K) koji predstavljaju indeks početka i kraj podniza knjiga, redom, za koji treba odgovoriti koliko različitih autora je učestvovalo u pisanju knjiga tog podniza.

Izlaz.

(Izlazne podatke upisati u datoteku knjige.out) U K redova ispisati odgovore na postavljena pitanja, u i-tom redu odgovor za podniz čiji su indeksi idxs_i i idxe_i iz ulaza.

Primer 1.

5 6
1 2 3 4 3
1 5
2 2
3 5
1 4
2 5
2 4

4
1
2
4
3
3

Primer 2.

4 3
1 1 12 12
1 4
1 2
3 4

2
1
1

Napomena.

• U 40% test primera jedinstveni brojevi autora će se kretati u intervalu [1, 60].
• U 30% test primera će i broj upita i broj različitih autora biti najviše 1000.
• U 60% test primera će biti ispunjen bar jedan od prethodna dva uslova.

/*
  Ovo je zvanicno resenje. Resenje je off-line.
  Slozenost resenja po upitu je O(log broj_autora).
  Nakon ucitavanja intervala, sortiramo sve intervale.
  Shodno tome, slozenost celog programa (gde je I 
  broj intervala, A broj autora, a N broj knjiga) je
  O(I * log A + I * log I + N)
*/
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <vector>
#define ffor(_a,_f,_t) for(int _a=(_f),__t=(_t);_a<__t;_a++)
#define all(_v) (_v).begin() , (_v).end()
#define sz size()
#define pb push_back
#define SET(__set, val) memset(__set, val, sizeof(__set))
#define FOR(__i, __n) ffor (__i, 0, __n)
#define syso system("pause")
#define mp make_pair

using namespace std;

const int MAXN = 100000;
const int MAXK = 100000;
const int TYPE_BOOK = 0;
const int TYPE_INTERVAL = 1;

struct myt{
  int s, e, val, type, idx;
  myt(){
    
  }
  
  myt(int _s, int _e, int _val, int _type, int _idx){
    s = _s;
    e = _e;
    val = _val;
    type = _type;
    idx = _idx;
  }
  
  friend bool operator <(const myt &a, const myt &b){
    if (a.e < b.e)
      return true;
    if (a.e > b.e)
      return false;
    if (a.type == TYPE_BOOK && b.type == TYPE_INTERVAL)
      return true;
    return false;
  }
  
};

int a[MAXN];

int bit[MAXN + 1];

void update(int idx, int val){
  while (idx <= MAXN){
    bit[idx] += val;
    idx += (idx & -idx);
  }
}

int read(int idx){
  int ret = 0;
  while (idx){
    ret += bit[idx];
    idx -= (idx & -idx);
  }
  
  return ret;
}

int lastIdx[MAXN];

myt vals[MAXN + MAXK];
int ret[MAXK];

int main(){
//  clock_t begin, end;
//  begin = clock() * CLK_TCK;

  freopen("knjige.out", "wt", stdout);
  freopen("knjige.in", "r", stdin);
  int n, k, v, cnt = 0;
  scanf("%d %d", &n, &k);
  FOR (i, n){
    scanf("%d", &v);
    v--;
    vals[cnt++] = myt(i + 1, i + 1, v, TYPE_BOOK, i);
  }
    
  // kroz sve upite
  int idxs, idxe;
  FOR (i, k){
    scanf("%d %d", &idxs, &idxe);
    vals[cnt++] = myt(idxs, idxe, -1, TYPE_INTERVAL, i);
  }
  
  sort(vals, vals + n + k);
  SET(lastIdx, 255);
  FOR (i, cnt)
    if (vals[i].type == TYPE_BOOK){
      v = vals[i].val;
      if (lastIdx[v] != -1)
        update(lastIdx[v], -1);
      lastIdx[v] = vals[i].s;
      update(lastIdx[v], 1);
    }
    else
      ret[vals[i].idx] = read(vals[i].e) - read(vals[i].s - 1);
      
  FOR (i, k)
    printf("%d\n", ret[i]);
    
//  end = clock() * CLK_TCK;
//  cout << (end - begin) / 1000.0 << endl;

  return 0;
}