#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(998244353)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
int gcd(int A,int B) {if(!B)return A;return gcd(B,A%B);}
const int MAXN = 5e5+5;
vector<ll>a;
VII t(4*MAXN);
ll res = 0;
ll r1 = 0;
void build(int v,int l,int r)
{
	if(l == r){
		t[v].pb(a[l]);
		return;
	}
	int mid = (l+r)/2;
	build(2*v,l,mid);
	build(2*v+1,mid+1,r);
	for(int x:t[2*v])t[v].pb(x);
	for(int x:t[2*v+1])t[v].pb(x);
	sort(all(t[v]));
}
void get(int v,int l,int r,int tl,int tr)
{
	if(l > r)return;
	if(tl==l && tr == r){
		int p = ub(all(t[v]),r1)-t[v].begin();
		res+=t[v].size()-p;
		return;
	}
	int tm = (tl+tr)/2;
	get(2*v,l,min(r,tm),tl,tm);
	get(2*v+1,max(l,tm+1),r,tm+1,tr);
}
int main()
{
	owo
	int n,q;
	cin>>n>>q;
	a.resize(n+1);
	vector<ll>occ(n+1,n+1);
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=n;i>0;i--){
		int tmp = a[i];
		a[i] = occ[a[i]];
		occ[tmp] = i;
	}
	build(1,1,n);
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		r1 = r;
		res = 0;
		get(1,l,r,1,n);
		cout<<res<<'\n';
	}
}


Measured memory_bytes: 160696