/*
 _     _                             
| |__ | |__   __ _  __ _ _   _  __ _ 
| '_ \| '_ \ / _` |/ _` | | | |/ _` |
| |_) | | | | (_| | (_| | |_| | (_| |
|_.__/|_| |_|\__,_|\__, |\__, |\__,_|
                   |___/ |___/       
*/
#include<bits/stdc++.h>

#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define BigInt      __int128
#define endl        '\n'
#define mii         map<ll int,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define sim         template < class c
#define ris         return * this
#define dor         > debug & operator <<
#define eni(x)      sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {

using namespace std;

sim > struct rge {c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug 
{
	~debug() 
	{ 
		cerr<<endl; 
	}
	eni(!=) cerr << boolalpha << i; ris; }
	eni(==) ris << range(begin(i), end(i)); }
	sim, class b dor(pair < b, c > d) 
	{
		ris << "(" << d.first << ", " << d.second << ")";
	}
	sim dor(rge<c> d) 
	{
	  	*this << "[";
	  	for (auto it = d.b; it != d.e; ++it)
	    	*this << ", " + 2 * (it == d.b) << *it;
	  	ris << "]";
	}
};
#define fuck(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define N  500005

int a[N],seg[N<<2];

void build(int node,int start,int end){
    if(start==end){
        seg[node]=a[start];
        return;
    }
    int mid=(start+end)>>1;
    build(node<<1,start,mid);
    build(node<<1|1,mid+1,end);
    seg[node]=seg[node<<1]+seg[node<<1|1];
}
int query(int node,int start,int end,int l,int r){
    if(l<=start && r>=end) return seg[node];
    if(r<start || l>end) return 0;
    int mid=(start+end)>>1;
    int ans1=query(node<<1,start,mid,l,r);
    int ans2=query(node<<1|1,mid+1,end,l,r);
    return (ans1+ans2);
}
void update(int node,int start,int end,int x,int val){
    if(start==end){
        a[x]+=val;
        seg[node]+=val;
        return;
    }
    int mid=(start+end)>>1;
    if(start<=x && x<=mid) update(node<<1,start,mid,x,val);
    else update(node<<1|1,mid+1,end,x,val);
    seg[node]=seg[node<<1]+seg[node<<1|1];
}

int last_occ[N];

int ans[N];

vector<pair<int, int>> queries[N]; // queries[i] contain queries with l,r whrere r = i; // <l, query_num>

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
	// cin>>TESTS;
	while(TESTS--)
	{
		int n, q;
		cin >> n >> q;
		int c[n + 1];
		for(int i = 1; i <= n; i++)
		{
			cin >> c[i];
		}
		for(int i = 1; i <= q; i++)
		{
			int l, r;
			cin >> l >> r;
			queries[r].pb({l, i});
		}

		memset(a, 0, sizeof(a));

		build(1, 1, n);

		for(int i = 1; i <= n; i++)
		{
			int prev = last_occ[c[i]];
			last_occ[c[i]] = i;
			int curr = last_occ[c[i]];
			if(prev >= 1) update(1, 1, n, prev, -1);
			update(1, 1, n, curr, +1);
			for(auto qq : queries[i])
			{
				ans[qq.S] = query(1, 1, n, qq.F, i);
			}
		}


		for(int i = 1; i <= q; i++)
		{
			cout << ans[i] << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 37364