#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,a[N],f[21][N];
int t[N];
int main(){
	freopen("dry.in","r",stdin);
	freopen("dry.out","w",stdout);
	scanf("%d%d",&n,&q);
	for(int i = 1;i<=n;i++) scanf("%d",&a[i]),f[0][i]=a[i];
	for(int i = 1;i<=19;i++)
	for(int j = 1;j+(1<<i)-1<=n;j++)
	f[i][j]=min(f[i-1][j],f[i-1][j+(1<<(i-1))]);
	while(q--){
		int l,r; scanf("%d%d",&l,&r);
		memset(t,0,sizeof(t));
		int ans=0;
		for(int i = l;i<=r;i++){
			if(a[i]==a[i-1]&&i!=l){t[a[i]]=i; continue;}
			if(!t[a[i]]) ans++,t[a[i]]=i;
			else{
				int s=log2(i-1-(t[a[i]]+1)+1);
				int val=min(f[s][t[a[i]]+1],f[s][i-1-(1<<s)+1]);
				if(val<a[i]) ans++,t[a[i]]=i;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}