#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#define ll long long
#define qwq 2000007
inline int read(){
	char c=getchar();
	int x=0;int flag=0;
	for(;c<'0'||c>'9';c=getchar())flag|=(c=='-');
	for(;c<='9'&&c>='0';c=getchar())x=(x<<1)+(x<<3)+c-'0';
	if(flag)return -x;
	return x;
}
int n,q;
int a[qwq];
int flag1[qwq];
struct Line{
	int l,r;
}b[qwq],c[qwq];
int cntb,cntc;
bool cmpLine(Line x,Line y){
	if(x.r!=y.r)return x.r<y.r;
	return x.l>y.l;
}
int L[qwq];
inline void add_line(int l,int r){
//	printf("add[%d,%d]\n",l,r);
	++cntb;
	b[cntb].l=l;b[cntb].r=r;
	return ;
}
struct ASK{
	int l,r;
	int num;
}ask[qwq];
bool cmpASK(ASK x,ASK y){
	return x.l<y.l;
}
int ans[qwq];
int T[qwq];
#define pii std::pair<int,int>
#define mp std::make_pair
std::priority_queue<pii>p_que;
int fa[qwq];
int get_f(int x){
	if(fa[x]==x)return x;
	return fa[x]=get_f(fa[x]);
}
struct tree{
	int son[2];
	int dis;
	int val;
	int tag;
}tr[qwq];
int merge(int x,int y){
	if(!x)return y;
	if(!y)return x;
	if(tr[x].val<tr[y].val)std::swap(x,y);
	if(tr[x].val==tr[y].val&&y>x)std::swap(x,y);
	tr[y].son[1]=merge(x,tr[y].son[1]);
	if(tr[tr[y].son[1]].dis>tr[tr[y].son[0]].dis)std::swap(tr[y].son[0],tr[y].son[1]);
	tr[y].dis=tr[tr[y].son[1]].dis+1;
	return y;
}
inline int delet(int x){
	x=get_f(x);
	return fa[x]=fa[tr[x].son[0]]=fa[tr[x].son[1]]=merge(tr[x].son[0],tr[x].son[1]);
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	} 
	int lasl=1,lasr=1;
	for(int i=2;i<=n;++i){
		if(a[i]==a[lasr])++lasr;
		else {
			add_line(lasl,lasr);
			lasl=i;lasr=i;
		}
	}
	add_line(lasl,lasr);
	for(int i=1;i<=cntb;++i){
		L[i]=b[i].l;
		if(b[i].l==b[i].r){
			flag1[b[i].l]=1;
		}
	}
	for(int i=1;i<=n;++i)flag1[i]+=flag1[i-1];
	for(int i=1;i<=cntb;++i){
		if(T[a[b[i].l]]){
			int l=T[a[b[i].l]];
			int r=i;
			if(flag1[r-1]-flag1[l]!=r-1-l)continue;
			++cntc;
			c[cntc].l=l,c[cntc].r=r;
		//	printf("[%d,%d]\n",l,r);
		}
		T[a[b[i].l]]=i;
	}
	std::sort(c+1,c+cntc+1,cmpLine);
	for(int i=1;i<=q;++i){
		int x=read(),y=read();
		if(x>y)std::swap(x,y);
		if(x==y){
			printf("%d\n",0);
			--q;--i;
			continue;
		}
		int l=std::upper_bound(L+1,L+cntb+1,x)-L-1;
		int r=std::upper_bound(L+1,L+cntb+1,y)-L-1;
		ans[i]=r-l+y-x;
		ask[i].l=l;ask[i].r=r;ask[i].num=i;
		int R=l,cnt=0;
		for(int j=1;j<=cntc;++j){
			if(c[j].r>r)continue;
			if(c[j].l>=R){
				R=c[j].r;++cnt;
			}
		}
		printf("%d\n",ans[i]-cnt);
	}
	
//	std::sort(ask+1,ask+q+1,cmpASK);
//	int lasask=1,lasc=1;
//	for(int r=1;r<=cntb;++r){
//		for(;lasask<=q&&ask[lasask].l==r;++lasask){
//			p_que.push(mp(-ask[lasask].l,lasask));
//			tr[lasask].val=ask[lasask].r;
//			fa[lasask]=lasask;
//		}
//		for(;lasc<=cntc&&c[lasc].r==r;++lasc){
//			while(!p_que.empty()){
//				int x=p_que.top().second,R=-p_que.top().first;
//				if(ask[lasask].r<r){
//					int x=delet(lasask);
//					if(x!=0)p_que.push(mp(-ask[x].r,x));
//					continue;
//				}
//			}
//		}
//	}	
	return 0;
}