#include<bits/stdc++.h>
#define N 200005
#define M 500
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,a[N],m,t[N],b[N],ans[N],cnt;
struct que
{
	int l,r,id;
	bool operator <(que a)const
	{
		if(l/M!=a.l/M)return l<a.l;
		if((l/M)%2)return r<a.r;
		return r>a.r;
	}
}k[N];
void midy(int a)
{
	if(t[a])cnt--,t[a]=0;
	else t[a]=1,cnt++;
}
signed main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read(),b[i]=a[i];
	sort(b+1,b+1+n);int len=unique(b+1,b+1+n)-b-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(b+1,b+1+len,a[i])-b;
	for(int i=1;i<=m;i++)k[i].l=read(),k[i].r=read(),k[i].id=i;
	sort(k+1,k+1+m);t[a[1]]=1;cnt=1;
	for(int i=1,l=1,r=1;i<=m;i++)
	{
//		cout<<k[i].l<<" "<<k[i].r<<"\n";
		while(l>k[i].l)midy(a[--l]);
		while(r<k[i].r)midy(a[++r]);
		while(l<k[i].l)midy(a[l++]);
		while(r>k[i].r)midy(a[r--]);
		ans[k[i].id]=(r-l+1-cnt)/2+cnt+cnt%2;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<"\n";
	return 0;
}