//created by fqr & cyx in 2024
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
#define ll long long
#define pb emplace_back
int ff,Ch;
template <typename T> inline void rd(T &x) {
    x=0,ff=1,Ch=getchar();
    while((Ch<'0'||Ch>'9') && Ch!='-') Ch=getchar();
    if(Ch=='-')Ch=getchar(),ff=-1;
    while(Ch>='0' && Ch<='9') {
        x=(x<<1)+(x<<3)+Ch-'0';
        Ch=getchar();
    }
    x*=ff;
}
template <typename T,typename ...Args> inline void rd(T &x,Args &...args) {
    rd(x), rd(args...);
}
using namespace std;
const int N=1e4+5;
int n,Q;
int mp[N];
int a[N];
signed main() {
//	freopen("color.in","r",stdin);
//	freopen("color.out","w",stdout);
	rd(n),rd(Q);
	for(int i=1,lst; i<=n; i++)
		rd(a[i]);
	int l,r;
	while(Q--) {
		rd(l),rd(r);	
		if(l>r) swap(l,r);
		memset(mp,0,sizeof(mp));
		int ans=r-l;
		for(int i=l+1; i<=r; i++)
			if(a[i]!=a[i-1])
				ans++;
		for(int i=l,p=0; i<=r; i++) {
			if(mp[a[i]]>p && mp[a[i]]!=i-1)
				ans--,p=i;
			mp[a[i]]=i;
		}
		printf("%d\n",ans);
	}
    return 0;
}
/*

*/