#include <cstdio>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
int N, Q;
struct range{
int start, end;
int id;
};
template<int add>
void update1(const vector<int>& types, vector<int>& heatmap, vector<int>& nbTypes, int& maxi, int index){
heatmap[max(0, nbTypes[types[index]])]--;
nbTypes[types[index]] += add;
heatmap[max(0, nbTypes[types[index]])]++;
if constexpr(add == 1){
if(heatmap[maxi+1])maxi++;
}else{
if(!heatmap[maxi])maxi--;
}
}
void update(const vector<int>& types, vector<int>& heatmap, vector<int>& nbTypes, int& maxi, range currange, range nextrange){
//printf("%d %d -> %d %d\n", currange.start, currange.end, nextrange.start, nextrange.end);
if(abs(currange.end-nextrange.end)+nextrange.start-currange.start > nextrange.end-nextrange.start+currange.end-currange.start){
for(int i=currange.start; i<currange.end; i++){
update1<-1>(types, heatmap, nbTypes, maxi, i);
}
for(int i=nextrange.start; i<nextrange.end; i++){
update1<1>(types, heatmap, nbTypes, maxi, i);
}
}else{
if(currange.end > nextrange.end){
for(int i=nextrange.end; i<currange.end; i++){
update1<-1>(types, heatmap, nbTypes, maxi, i);
}
}else{
for(int i=currange.end; i<nextrange.end; i++){
update1<1>(types, heatmap, nbTypes, maxi, i);
}
}
for(int i=currange.start; i<nextrange.start; i++){
update1<-1>(types, heatmap, nbTypes, maxi, i);
}
}
}
range updatesubtree(const vector<range>& rangesT, const vector<int>& types, vector<int>& heatmap, vector<int>& nbTypes, int& maxi, vector<int>& res, range currange, int id){
update(types, heatmap, nbTypes, maxi, currange, rangesT[id]);
int nb1 = heatmap[1];
int nb2p = N-heatmap[0]-heatmap[1];
int size = rangesT[id].end-rangesT[id].start;
if(maxi*2 >= size){
res[id] = heatmap[maxi] == 1;
}else{
res[id] = nb2p;
if(size%2 == 1)
res[id] += nb1;
}
return rangesT[id];
}
int main(){
scanf("%d %d\n", &N, &Q);
vector<int> types(N);
for(int i=0; i<N; i++){
scanf("%d", &types[i]);
types[i]--;
}
vector<int> sortedIds(Q);
vector<range> rangesT(Q);
for(int i=0; i<Q; i++){
scanf("%d%d", &rangesT[i].start, &rangesT[i].end);
rangesT[i].start--;
sortedIds[i] = i;
}
sort(sortedIds.begin(), sortedIds.end(), [&](int a, int b){return rangesT[a].start < rangesT[b].start;});
vector<int> res(Q, -1);
vector<int> jumps(Q+1);
for(int i=0; i<Q+1; i++){
jumps[i] = i+1;
}
while(jumps[0] != Q+1){
range lastrange = {0, 0, -1};
vector<int> nbTypes(N);
int nb2p = 0;
int nb1 = 0;
vector<int> heatmap(N*2+1);
heatmap[0] = N;
int maxi = 0;
int last = 0;
bool godown = false;
for(int i=jumps[0]; i<Q+1; i = jumps[i]){
if(rangesT[sortedIds[i-1]].end < lastrange.end){
if(godown){
last = i;
continue;
}
}else{
godown = true;
}
jumps[last] = jumps[i];
lastrange = updatesubtree(rangesT, types, heatmap, nbTypes, maxi, res, lastrange, sortedIds[i-1]);
}
}
for(int i=0; i<Q; i++){
printf("%d\n", res[i]);
}
}
