//2020年4月17日現在

#include<stdio.h>
#include<cmath>
#include<math.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<complex>
#include<queue>
#include<set>
#include<utility>
#include<iomanip>
#include<limits>
#include<thread>
#include<map>
#include<stack>
#include<numeric>
#include<cassert>
#include<random>
#include<chrono>
#include<unordered_set>
#include<unordered_map>
#include<fstream>
#include<list>
#include<functional>
#include<bitset>
#include<tuple>
#include <cstdio>

using namespace std;

template <class... A>
void prints() { cout << "\n"; }
template <class... A>
void prints_rest() { cout << "\n"; }
template <class T, class... A>
void prints_rest(const T &first, const A &... rest) { cout << " " << first; prints_rest(rest...); }
template <class T, class... A>
void prints(const T &first, const A &... rest) { cout << first; prints_rest(rest...); }
template <class T, class... A>
void printd(const T &first, const A &... rest) { cout << fixed << setprecision(15) << first; prints_rest(rest...); }


namespace {
	// printElems(&a[0], &a[n]);　みたいな感じで使う。
	void printElems(const int* begin, const int* end)
	{
		for (const int* p = begin; p != end; ++p) {
			cout << *p << ' ';
		}
		cout << endl;
	}
}

#define rep(i,n) for(ll i=0; i<n; i++)
#define rep1(i,n) for(ll i=1; i<n+1; i++)
#define repr(i,n) for(ll i=n-1; i>=0; i--)
#define repr1(i,n) for(ll i=n; i>0; i--)
#define FOR(i,j,n) for(ll i=j; i < n; i++)
#define souatari(i,j,n) rep1(i,n-1)rep(j,i)
#define souatari1(i,j,n) for(ll i=2; i<n+1; i++)rep1(j,i-1)
#define mp make_pair
#define F first
#define S second
#define elif else if

typedef long long ll;
typedef vector<int>  vi;
typedef vector<vi>  vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef array<int,3> arr3;
typedef long double D;


const ll llinf =  numeric_limits<ll>::max();
const ll _llinf = numeric_limits<ll>::lowest();
const int inf = numeric_limits<int>::max();
const int _inf = numeric_limits<int>::lowest();
const double dinf = numeric_limits<double>::infinity();
const ll MOD = 1000000007;
//const ll MOD = 998244353;
const ll BIG = 1LL<<60;
const string yes = "Yes";
const string no = "No";

//----------------------------------------------

//BIT bit(16384);みたいな感じで生成する
struct BIT {
	typedef int T;
	T n;
	vector<T> bit;

	// 各要素の初期値は 0
	BIT(T num) : bit(num+1, 0) { n = num; }

	// a_i += w
	void add(T i, T w) {
		for (T x = i; x <= n; x += x & -x) {
			bit[x] += w;
		}
	}

	// [1, i] の和を計算.
	T sum(T i) {
		T ret = 0;
		for (T x = i; x > 0; x -= x & -x) {
			ret += bit[x];
		}
		return ret;
	}

	//[iより大きい]の和を計算
	T sum_above(T i) {
		T ret = 0;
		for (T x = i; x > 0; x -= x & -x) {
			ret += bit[x];
		}
		return sum(n) - ret;
	}

};



int c[500005];
int l[500005];

vector<pii> v[500005];
int ans[500005];


int main(){
	BIT bit(524288);



	int n,q;
	cin >> n >> q;

	map<int,int> m;
	rep1(i,n){
		cin >> c[i];

		decltype(m)::iterator it = m.find(c[i]);
		if(it != m.end()){
			//存在する時
			l[i] = m[c[i]];
			m[c[i]] = i;
		}
		else{
			//存在しない時
			m.insert(mp(c[i],i));
		}
	}
	rep(i,q){
		int ltmp,rtmp;
		cin >> ltmp >> rtmp;
		v[rtmp].push_back(mp(i,ltmp));
	}


	rep1(i,n){
		bit.add(i,1);
		if(l[i]!=0)bit.add(l[i],-1);
		if(!v[i].empty()){
			int tmpsum = bit.sum(i);
			for(pii x : v[i]){
				if(x.S == 1) {ans[x.F] = tmpsum;}
				else{ans[x.F] = tmpsum-bit.sum(x.S-1);}
			}
		}
	}
	rep(i,q){
		prints(ans[i]);
	}

	return 0;
}




Measured memory_bytes: 54812