#include<bits/stdc++.h>
using namespace std;

#define QwQ330AwA return 0
#define ll long long

const int N = 2e5 + 5;
int n, m;
int bel[N];
int w[N];
struct Ask {
	int l, r, id;
	bool operator < (const Ask rhs) const {
		if (bel[l] == bel[rhs.l]) return r < rhs.r;
		else return bel[l] < bel[rhs.l];
	}
} q[N];
int ans[N];
int cnt[N];
int tot;
int sum;
map <int, int> lsh;
int res;
void add(int x) {
	if (cnt[x] & 1) tot--, sum++;
	else tot++;
	cnt[x]++;
}

void del(int x) {
	if (cnt[x] & 1) tot--;
	else tot++, sum--;
	cnt[x]--;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int B = sqrt(n);
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
		if (!lsh[w[i]]) lsh[w[i]] = ++res;
		w[i] = lsh[w[i]];
		bel[i] = (i - 1) / B + 1;
	}
	for (int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r, 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) add(w[++r]);
		while (l > q[i].l) add(w[--l]);
		while (l < q[i].l) del(w[l++]);
		while (r > q[i].r) del(w[r--]);
		ans[q[i].id] = sum + ((tot + 1) / 2) * 2;
	}
	for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
	QwQ330AwA;
}