#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>   
using namespace std;
using namespace __gnu_pbds;
typedef int ll; 
// #define int long long
typedef unsigned long long lu;
typedef vector<ll> v;
typedef vector<vector<ll> > vv;
typedef vector<string>  vs;
typedef vector<pair<ll,ll>> vpr;
typedef vector<bool>vb;
typedef vector<double>vd;
typedef long double ld;
#define f(i,n) for(ll i = 0; i < n; i++)
#define ff(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define amax(x,y) if(y>x) x=y;
#define amin(x,y) if(y<x)x=y;
#define bg(x) x.begin()
#define sz(x) (ll)x.size()
#define in(x,n) for(ll i=0;i<n;i++)cin>>x[i]
#define out(x,n) for(ll i=0;i<n;i++)cout<<x[i]<<" " 
#define mxt(a) *(max_element(a.begin(),a.end()))
#define mnt(a) *(min_element(a.begin(),a.end())
#define tc ll t;cin>>t;while(t--)
typedef pair<ll,ll> pi;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define yesno(f) if(f) yes else no
const v dx = {1, -1, 0, 0};
const v dy = {0, 0, 1, -1};
const ld PI = 2 * acos(0.0);
ll cel(ll x1,ll y1){if((x1%y1)==0)return x1/y1;else return x1/y1+1;}
ll power(ll a,ll b,ll m)
{
    if(b==0)
        return 1;
    ll d=power(a,b/2,m);
    d=(d*d)%m;
    if(b&1)
        d=(d*a)%m;
    return d;
}
const ll mod=1e9+7;
int MOD(int a)
{
    if(a<0)
        a+=mod;
    if(a>=mod)
        a%=mod;
    return a;
}
// set_name.find_by_order(k) It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time
// set_name.order_of_key(k) It returns to the number of items that are strictly smaller than our item k in O(logn) time.
/*string operations :
str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
str.substr (x) : returns a substring str[x],... end of string
str.find(qtr) : returns the first occurenece of qtr in str */
int Nodes=0;
const int N=4e7+1;
int seg[N],lp[N],rp[N];
int build(int ss,int se)
{
	int pos=Nodes++;
	if(ss==se)
	{
		seg[pos]=0;
		lp[pos]=-1;
		rp[pos]=-1;
		return pos;
	}
	int mid=(ss+se)/2;
	lp[pos]=build(ss,mid);
	rp[pos]=build(mid+1,se);
	seg[pos]=0;
	// seg[pos]=seg[lp[pos]]+seg[rp[pos]];
	return pos;
}
int update(int root,int ss,int se,int ind,int val){
	if(ind < ss || ind > se)
		return root;
	int pos=Nodes++;
	if(ss == se)
	{
		seg[pos]=val;
		return pos;
	}
	int mid=(ss+se)/2;
	if(ind <=mid)
	{
		lp[pos]=update(lp[root],ss,mid,ind,val);
		rp[pos]=rp[root];
		seg[pos]=seg[lp[pos]]+seg[rp[pos]];
		return pos;
	}
	else
	{
		rp[pos]=update(rp[root],mid+1,se,ind,val);
		lp[pos]=lp[root];
		seg[pos]=seg[lp[pos]]+seg[rp[pos]];
		return pos;
	}
}
int query(int pos,int ss,int se,int l,int r)
{
	if(l <=ss && r>=se)
	{
		return seg[pos];
	}
	if(l > se || r < ss)
		return 0;
	int mid=(ss+se)/2;
	return query(lp[pos],ss,mid,l,r)+query(rp[pos],mid+1,se,l,r);
}
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n,q;cin>>n>>q;
    v arr(n);in(arr,n);
    v next(n,n);
    map<int,int>mapp;
    for(int i=n-1;i>=0;i--)
    {
    	if(mapp.count(arr[i]))
    		next[i]=mapp[arr[i]];
    	mapp[arr[i]]=i;
    }
    v roots;
    int root=build(0,n-1);
    // roots.pb(root);
    for(int i=n-1;i>=0;i--)
    {
    	root=update(root,0,n-1,i,1);
    	if(next[i]!=n)
    	{
    		root=update(root,0,n-1,next[i],0);
    	}
    	roots.pb(root);
    }
    reverse(all(roots));
    while(q--)
    {
    	int l,r;cin>>l>>r;
    	cout<<query(roots[l-1],0,n-1,l-1,r-1)<<endl;
    }
    return 0;
}

Measured memory_bytes: 254708