#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<cmath>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<numeric>
#include<functional>
#include<algorithm>
#include<bitset>
#include<tuple>
#include<unordered_set>
#include<unordered_map>
#include<random>
#include<array>
#include<cassert>
using namespace std;
#define INF ((1<<30)-1)
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(),v.end()




inline int popCount(unsigned int x) {
	x = x - ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	x = (x + (x >> 4)) & 0x0F0F0F0F;
	x = x + (x >> 8);
	x = x + (x >> 16);
	return x & 0x0000003F;
}


//メモリ使用量:2nビット
class BitVector {
	int n;
	int blocks;
	vector<unsigned int> B;
	vector<int> r;
public:
	BitVector() {}
	BitVector(int size) {
		init(size);
	}
	void init(int size) {
		n = size;
		blocks = (n >> 5) + 1;
		B.assign(blocks, 0);
		r.assign(blocks, 0);
	}
	void set(int k) {
		B[k >> 5] |= 1 << (k & 31);
	}
	void build() {
		r[0] = 0;
		for (int i = 1; i < blocks; i++) {
			r[i] = popCount(B[i - 1]) + r[i - 1];
		}
	}
	bool access(int k)const {
		return B[k >> 5] & 1 << (k & 31);
	}
	//[0,k)の1の個数
	int rank(int k)const {
		return r[k >> 5] + popCount(B[k >> 5] & ((1 << (k & 31)) - 1));
	}
};


//ウェーブレット行列
class WaveletMatrix {
	typedef int Val;
	static const Val NIL = -1;
	static const int BITLEN = 20;
	int len;
	BitVector bv[BITLEN];
	int encode(Val c)const {
		return c;
	}
	Val decode(int n)const {
		return n;
	}
	struct Node {
		int height, s, e, code;
		Node() {}
		Node(int a, int b, int c, int d) :height(a), s(b), e(c), code(d) {};
		bool operator <(Node a)const { return e - s < a.e - a.s; }
	};
public:
	int length()const {
		return len;
	}
	WaveletMatrix() {
	}
	template<class T>
	WaveletMatrix(const T& v) {
		init(v);
	}
	//O(n logσ)
	template<class T>
	void init(const T& v) {
		len = v.size();
		for (int i = 0; i < BITLEN; i++) {
			bv[i].init(v.size());
		}
		int* bucket;
		bucket = new int[2 * len];
		int* cur, * next;
		cur = bucket;
		next = bucket + len;
		int rank0[BITLEN] = { 0 };
		for (int i = 0; i < len; i++) {
			int n = encode(v[i]);
			cur[i] = n;
			for (int j = BITLEN - 1; j >= 0; j--) {
				if ((n & 1 << j) == 0)rank0[j]++;
			}
		}
		for (int i = BITLEN - 1;; i--) {
			for (int j = 0; j < len; j++) {
				if (cur[j] & 1 << i)bv[i].set(j);
			}
			bv[i].build();
			if (i == 0)break;
			int idx0 = 0, idx1 = rank0[i];
			for (int j = 0; j < len; j++) {
				if (cur[j] & 1 << i)next[idx1++] = cur[j];
				else next[idx0++] = cur[j];
			}
			swap(cur, next);
		}
		delete[] bucket;
	}
	//[s,e)中のx未満の文字の個数
	int rank_lt(int s, int e, Val x)const {
		int n = encode(x);
		int res = 0;
		for (int i = BITLEN - 1; i >= 0; i--) {
			int ssum = bv[i].rank(s);
			int esum = bv[i].rank(e);
			if (n & 1 << i) {
				res += e - s - (esum - ssum);
				s = len - bv[i].rank(len) + ssum;
				e = s + esum - ssum;
			}
			else {
				s = s - ssum;
				e = e - esum;
			}
			if (s == e)return res;
		}
		return res;
	}
	//[s,e)中の x<=c<y となる文字の個数
	//O(logσ)
	int rangefreq(int s, int e, Val x, Val y)const {
		return rank_lt(s, e, y) - rank_lt(s, e, x);
	}
};




int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

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

	vector<int> v;
	unordered_map<int, int> mp;

	rep(i, n) {
		int c;
		cin >> c;
		v.push_back(mp[c]);
		mp[c] = i + 1;
	}
	WaveletMatrix wm(v);

	rep(i, q) {
		int l, r;
		cin >> l >> r;
		cout << wm.rank_lt(l - 1, r, l) << endl;
	}


	return 0;
}


Measured memory_bytes: 31068