#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <vector>
#include <bitset>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <deque>
#include <string>
#include <list>
#include <iterator>
#include <algorithm>
#include <unordered_map>
#define int                long long
#define pb                 push_back
#define pi                 pair<int,int>
#define vi                 vector<int>
#define all(v)             v.begin(),v.end()
#define MOD                1000000007
#define F                  first
#define S                  second
#define FOR(i,r)           for(int i=0;i<r;i++)
#define REP(i,l,r)         for(int i=l;i<r;i++)
#define RER(i,l,r)         for(int i=l;i>=r;i--)
#define print(v)           for(auto i : v)cout << i << ' ';
#define FASTIO             ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mem(arr,k)         memset(arr,k,sizeof(arr));
#define pii                acos(-1.0)
#define PI                 3.1415926535897932385
#define Sin(a)             sin((pi*a)/180)
#define test()             int x;cin >> x;while(x--){solve();}
#define test2()            int x;cin >> x;for(int i=1;i<=x;i++){cout << "Case #" << i << " : ";solve();}
#define watch(x)           cout << (#x) << " is " << (x) << endl
using namespace std;


/* Mathematical Functions */
int power(int x,int y);
bool isPrime(int n);
int modInv(int a,int b);
int gcdExtended(int a,int b,int *x,int* y);
int mpower(int a,int b,int p);

const int inf = (int)1e17;
const int N = (int)3e6+5;
int n;
vector<int>BIT(N,0),lastvis(N,-1),ans(N);
void update(int i,int x)
{
	for(;i<=n;i+=(i&(-i))){
		BIT[i] += x;
	}
}
int sum(int i)
{
	int ans = 0;
	for(;i>0;i-=(i&(-i))){
		ans += BIT[i];
	}
	return ans;
}
int query(int l,int r){
	return sum(r)-sum(l-1);
}
int32_t main(){

	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
	FASTIO;
	int q;
	cin >> n >> q;
	//int q;
	vector<int>v(n);
	REP(i,0,n){
		cin >> v[i];
	}
	//cin >> q;
	vector<pair<pi,int> >quer;
	REP(i,0,q){
		int x,y;
		cin >> x >> y;
		quer.pb({{y,x},i});
	}
	sort(all(quer));
	int cnt = 0;
	REP(i,0,n){
		if(lastvis[v[i]] != -1){
			update(lastvis[v[i]]+1,-1);
		}
		lastvis[v[i]] = i;
		update(i+1,1);
		while(cnt < q && quer[cnt].F.F == i+1){
			ans[quer[cnt].S] = query(quer[cnt].F.S,quer[cnt].F.F);
			cnt++;
		}
	}
	REP(i,0,q){
		cout << ans[i] << endl;
	}
    return 0;

}
int modInv(int a, int m)
{
int x, y;
int g = gcdExtended(a, m, &x, &y);
int res = (x%m + m) % m;
return res;
}
 
int gcdExtended(int a, int b, int *x, int *y)
{
if (a == 0){
    *x = 0, *y = 1;
    return b;
  }
  int x1, y1;
  int gcd = gcdExtended(b%a, a, &x1, &y1);
  *x = y1 - (b/a) * x1;
  *y = x1;
  return gcd;
}
 
int mpower(int x, int y, int p)
{
int res = 1;
x = x % p;
while(y > 0){
    if(y & 1) res = (res*x) % p;
      y = y>>1;
      x = (x*x) % p;
    }
    return res;
}
int power(int x, int y)
{
int res = 1;
while (y > 0){
    if (y & 1) res = res*x;
      y = y>>1;
      x = x*x;
    }
    return res;
}
 
bool isPrime(int n)
{
if (n <= 1)  return false;
  if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
      int p=sqrt(n);
      for(int i=5;i<=p;i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
          return false;
      return true;
}

Measured memory_bytes: 90004