#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define fi first
#define se second
#define eb emplace_back
#define bp __builtin_parity
#define y1 yyl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
typedef bitset<509> bset;
typedef pair<bset,bset> v2;

int read() {
	int x=0,w=1; char c=getchar();
	while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
	while(isdigit(c)) {x=x*10+c-'0'; c=getchar();}
	return x*w;
}

const int N=1e6+9;
int n,m,q,a[N],b[N],nxt[N],lst[N],vst[N];

signed main() {
	n=read(), q=read();
	rep(i,1,n) a[i]=read(), m=max(m,a[i]);
	rep(i,1,q) {
		int l=read(), r=read();
		rep(i,1,n) b[i]=lst[i]=nxt[i]=0;
		if(l>r) {
			rep(i,r,l) b[i]=a[i];
			swap(l,r);
			reverse(b+l,b+r+1);
		} else {
			rep(i,l,r) b[i]=a[i];
		}
		int cnt=0;
		per(i,r,l) {
			nxt[i]=lst[b[i]];
			lst[b[i]]=i;
		}
		rep(i,l,r) {
			if(!nxt[i]) continue;
			else {
				rep(j,1,m) vst[i]=0;
				bool flag=1;
				rep(j,i+1,nxt[i]-1) {
					if(vst[b[j]]) {flag=0; break;}
					vst[b[j]]=0;
				}
				if(!flag) continue;
				rep(j,i+1,nxt[i]-1) cnt++, b[j]=b[i];
				i=nxt[i]-1;
			}
		}
		rep(i,l,r-1) if(b[i]!=b[i+1]) cnt++;
		printf("%lld\n",r-l+cnt);
	}
	return 0;
}