#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
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;
}
const int N = 2e5+5;
int n,m;
int bel[N],cnt[N],a[N],lsh[N];
int L[N],R[N],ans[N];
struct aa{
	int l,r,id;
	bool operator<(const aa&x)const{
		if(bel[l]==bel[x.l]){
			return r<x.r;
		}else{
			return bel[l]<bel[x.l];
		}
	}
}node[N];
int sum;
void upd(int x){
	if(cnt[a[x]]&1){
		sum++;
	}
	cnt[a[x]]++;
}
void del(int x){
	cnt[a[x]]--;
	if(cnt[a[x]]&1){
		sum--;
	}
}
int main(){
	n = read();m = read();
	for(int i=1;i<=n;i++){
		a[i] = read();
		lsh[i] = a[i];
	}
	sort(lsh+1,lsh+1+n);
	int z = unique(lsh+1,lsh+1+n)-lsh-1; 
	for(int i=1;i<=n;i++){
		a[i] = lower_bound(lsh+1,lsh+1+z,a[i])-lsh;
	}
	int sz = sqrt(n);
	for(int i=1;i<=n;i++){
		bel[i] = (i-1)/sz+1;
		if(!L[bel[i]]){
			L[bel[i]] = i;
		}
		R[bel[i]] = i;
	} 
	for(int i=1;i<=m;i++){
		int l,r;
		l = read();r = read();node[i] = (aa){l,r,i};
	}
	sort(node+1,node+1+m);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		int ll = node[i].l,rr = node[i].r;
		while(l>ll){
			upd(--l);
		}
		while(r<rr){
			upd(++r);
		}
		while(l<ll){
			del(l++); 
		}
		while(r>rr){
			del(r--);
		}
		ans[node[i].id] = sum+(r-l+1-sum*2)/2*2+((r-l+1-sum*2)&1)*2;
	}
	for(int i=1;i<=m;i++){
		cout<<ans[i]<<"\n";
	}
	return 0;
}