#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;
struct tree{
	int son[2];
	int dis;
	int val;
	int tag;
	int ans;
}tr[qwq];
inline void add_v(int x,int v){
	tr[x].tag+=v;
	tr[x].ans+=v;
	return ;
}
inline void pushdown(int x){
	if(tr[x].tag){
		if(tr[x].son[0])add_v(tr[x].son[0],tr[x].tag);
		if(tr[x].son[1])add_v(tr[x].son[1],tr[x].tag);
		tr[x].tag=0;
	}
	return ;
}
int merge(int x,int y){
	if(!x)return y;
	if(!y)return x;
	pushdown(x);
	pushdown(y);
	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;
}
int flagdel[qwq];
inline int delet(int x){
	flagdel[x]=1;
	pushdown(x);
	return merge(tr[x].son[0],tr[x].son[1]);
}
void dfs_pushdown(int x){
	pushdown(x);
	if(tr[x].son[0]){
		dfs_pushdown(tr[x].son[0]);
	}
	if(tr[x].son[1]){
		dfs_pushdown(tr[x].son[1]);
	}
	return ;
}
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[b[r].l-1]-flag1[b[l].r]==b[r].l-1-b[l].r){
				++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);
	int num=0;
	for(int i=1;i<=q;++i){
		++num;
		int x=read(),y=read();
		if(x>y)std::swap(x,y);
		if(x==y){
			--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;
	//	printf("[%d,%d]\n",l,r);
		ans[num]=r-l+y-x;
		ask[i].l=l;ask[i].r=r;ask[i].num=num;
//		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);
//	for(int i=1;i<=q;++i){
//		printf("ask[%d,%d]:%d\n",ask[i].l,ask[i].r,ask[i].num);
//	}
	int lasask=1,lasc=1;
	for(int r=1;r<=cntb;++r){
	//	printf("nowwork%d\n",r);
		for(;lasask<=q&&ask[lasask].l==r;++lasask){
			p_que.push(mp(-ask[lasask].l,lasask));
			tr[lasask].val=ask[lasask].r;
		}
	//	printf("qwq\n");
		for(;lasc<=cntc&&c[lasc].r==r;++lasc){
			int nowx=0;
			while(!p_que.empty()){
				int x=p_que.top().second,R=-p_que.top().first;
				if(ask[x].r<r){
					int x=delet(x);
					p_que.pop();
					if(x!=0)p_que.push(mp(-R,x));
					continue;
				}
				if(R>c[lasc].l){
					break;
				}
			//	printf("nowget:%d\n",x);
				nowx=merge(nowx,x);
				p_que.pop();
			}
			if(nowx!=0){
				add_v(nowx,1);
				p_que.push(mp(-c[lasc].r,nowx));
			}
		}
	}
//	printf("initOK\n");
	while(!p_que.empty()){
		int x=p_que.top().second;
		dfs_pushdown(x);
		p_que.pop();
	}
	for(int i=1;i<=q;++i){
		ans[ask[i].num]-=tr[i].ans;
	//	printf("%d:%d\n",ask[i].num,tr[i].ans);
	}
	for(int i=1;i<=num;++i){
		printf("%d\n",ans[i]);
	}
	return 0;
}