#include<bits/stdc++.h>
using namespace std;
int B=500;
struct query{
	int l,r,id;
	bool operator <(const query &o)const{
		if(l/B!=o.l/B)return l/B<o.l/B;
		if((l/B)&1)return r>o.r;
		return r<o.r;
	}
}q[200005];
int ans[200005];
int n,m; 
int a[200005];
int cnt[200005];
int sum1=0,sum2=0;
void ins(int x){
	cnt[a[x]]++;
	if(cnt[a[x]]&1)sum1++;
	else sum1--,sum2++;
}
void del(int x){
	cnt[a[x]]--;
	if(cnt[a[x]]&1)sum1++,sum2--;
	else sum1--;
}
int dc[200005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)dc[i]=a[i];
	sort(dc+1,dc+n+1);
	int len=unique(dc+1,dc+n+1)-dc-1;
	for(int i=1;i<=n;i++)a[i]=lower_bound(dc+1,dc+len+1,a[i])-dc;
	for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r);
	for(int i=1;i<=m;i++)q[i].id=i;
	sort(q+1,q+m+1);
	int L=1,R=0;
	for(int i=1;i<=m;i++){
		while(R<q[i].r)ins(++R);
		while(L>q[i].l)ins(--L);
		while(R>q[i].r)del(R--);
		while(L<q[i].l)del(L++);
		ans[q[i].id]=sum2+(sum1+1)/2*2;
	}
	for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
	return 0;
	//quod erat demonstrandum
}