//? https://ac.nowcoder.com/acm/contest/20322/J??

#include <algorithm>

#include <iostream>

#include <cstring>

?#include <vector>

?#define endl '\n'

?

using namespace std;

const int maxn = 1e5 + 9;?

int n, m;

int first[maxn], lst[maxn], a[maxn], ans[maxn];

int cnt;

int c[maxn];

struct node{

? ? int l, r, id;

? ? bool operator<(const node &B){

? ? ? ? return r < B.r;

? ? }

}d[maxn];

?// 樹狀數(shù)組更新

/*

for(? i=1;i<=16;i++)

? ? ? ? printf("i =%2d,i&(-i) =%2d\n",i,i&(-i));

i&(-i) 給出 i 最低位的權(quán)重

*/

void update(int i, int k){

? ? while(i <= n) c[i] += k, i += i & (-i);? ? // 父節(jié)點

}

int qry(int i){

? ? int ans = 0;

? ? // 子節(jié)點, 如果i=3, 下一個節(jié)點為i=2

? ? while(i) ans += c[i], i -= i & (-i);? ??

? ? return ans;?

}

?

void work()

{

? ? ?cnt = 0;

? ? memset(first,0 ,sizeof first);

? ? ?memset(lst,0 ,sizeof lst);

? ? memset(c,0 ,sizeof c);

? ??

? ? for(int i = 1; i <= n; ++i){

? ? ? ? cin >> a[i];

? ? ? ? if(!first[a[i]]) first[a[i]] = i, ++cnt;

? ? ? ? lst[a[i]] = i;??

? ? }

? ? for(int i = 1; i <= m; ++i){

? ? ? ? cin >> d[i].l >> d[i].r;

? ? ? ? d[i].id = i;

? ? }

? ? sort(d + 1, d + 1 + m);

? ? int j = 1;

? ? for(int i = 1; i <= n; ++i){

? ? ? ? while(i == d[j].r && j <= m){// 因為數(shù)據(jù)包含 [r,n]，所以先求答案再更新?

? ? ? ? ? ? ans[d[j].id] = cnt + qry(d[j].l);

? ? ? ? ? ? ++j;? ? // j不能減少，所以按照d[j].r排序

? ? ? ? }

? ? ? ? if(lst[a[i]] == i){

? ? ? ? ? ? update(first[a[i]], 1);

? ? ? ? ? ? --cnt;

? ? ? ? }

? ? }

? ? for(int i = 1; i <= m; ++i) //cout << ans[i] << endl;

? ? ? ?printf("%d\n" ,ans[i] );

}?

int main()

{? ?

? ? while(cin >> n >> m)

? ? work();

? ? return 0;

}