# include <bits/stdc++.h>
# define int long long
# define vi vector<int>
# define pb push_back
# define pii pair<int, int>
# define fi first
# define se second
# define endl '\n'
# define jess ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int n, q, a[2005], f[2005][2005];
void solve () {
cin >> n >> q;
for(int i=1; i<=n; i++) {
cin >> a[i];
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
f[i][j]=f[i-1][j];
}
f[i][a[i]]++;
}
for(int i=1; i<=q; i++) {
int l, r; cin >> l >> r;
int mx=0,cnt=0;
vi v;
for(int j=1; j<=n; j++) {
int tmp=f[r][j]-f[l-1][j];
mx=max(mx, tmp);
if(tmp>=2) cnt++;
if(tmp!=0) v.pb(tmp);
}
sort(v.begin(), v.end(), greater<int>());
int sz=r-l+1;
if(sz%2==0) {
if(mx<=(sz/2 - 1)) {
cout << cnt << endl;
}
else if(v.size()==1) {
cout << 1 << endl;
}
else if(v[0]==v[1]) cout << 0 << endl;
else {
cout << 1 << endl;
}
} else {
if(mx<=(sz/2)) {
cout << v.size() << endl;
} else {
cout << 1 << endl;
}
}
}
}
signed main() {
jess;
solve();
}
