#include <algorithm>
#include <iostream>
#include <set>
#include <utility>
#include <vector>
using namespace std;
struct Candidate {
int value = 0;
int count = 0;
};
Candidate mergeCandidate(Candidate a, Candidate b) {
if (a.count < b.count) {
swap(a, b);
}
if (a.value == b.value) {
a.count += b.count;
} else {
a.count -= b.count;
}
return a;
}
struct SegmentTree {
explicit SegmentTree(const vector<int>& arr) : n(static_cast<int>(arr.size()) - 1) {
tree.resize(4 * n + 5);
build(1, 1, n, arr);
}
void build(int node, int left, int right, const vector<int>& arr) {
if (left == right) {
tree[node] = {arr[left], 1};
return;
}
int mid = (left + right) >> 1;
build(node << 1, left, mid, arr);
build(node << 1 | 1, mid + 1, right, arr);
tree[node] = mergeCandidate(tree[node << 1], tree[node << 1 | 1]);
}
Candidate query(int node, int left, int right, int ql, int qr) const {
if (ql == left && qr == right) {
return tree[node];
}
int mid = (left + right) >> 1;
if (qr <= mid) {
return query(node << 1, left, mid, ql, qr);
}
if (ql > mid) {
return query(node << 1 | 1, mid + 1, right, ql, qr);
}
return mergeCandidate(
query(node << 1, left, mid, ql, mid),
query(node << 1 | 1, mid + 1, right, mid + 1, qr)
);
}
Candidate query(int left, int right) const {
return query(1, 1, n, left, right);
}
int n;
vector<Candidate> tree;
};
struct Fenwick {
explicit Fenwick(int n) : bit(n + 1, 0) {}
void add(int idx, int delta) {
for (int x = idx; x < static_cast<int>(bit.size()); x += x & -x) {
bit[x] += delta;
}
}
int query(int idx) const {
int result = 0;
for (int x = idx; x > 0; x -= x & -x) {
result += bit[x];
}
return result;
}
vector<int> bit;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> arr(n + 1);
for (int i = 1; i <= n; ++i) {
cin >> arr[i];
}
vector<vector<int>> positions(n + 1);
for (int i = 1; i <= n; ++i) {
positions[arr[i]].push_back(i);
}
SegmentTree seg(arr);
vector<int> answer(q, -1);
vector<vector<pair<int, int>>> queriesStartingAt(n + 2);
for (int idx = 0; idx < q; ++idx) {
int l, r;
cin >> l >> r;
queriesStartingAt[l].push_back({r, idx});
set<int> candidates;
candidates.insert(arr[l]);
if (l + 1 <= r) {
candidates.insert(seg.query(l + 1, r).value);
}
set<int> balanced;
for (int value : candidates) {
if (value == 0) {
continue;
}
const auto& pos = positions[value];
int cnt = static_cast<int>(
upper_bound(pos.begin(), pos.end(), r) -
lower_bound(pos.begin(), pos.end(), l)
);
if (cnt * 2 >= (r - l + 1)) {
balanced.insert(value);
}
}
if (balanced.size() == 1U) {
answer[idx] = 1;
} else if (balanced.size() == 2U) {
answer[idx] = 0;
}
}
Fenwick firstOcc(n), secondOcc(n);
vector<int> firstPos(n + 1, -1), secondPos(n + 1, -1);
for (int l = n; l >= 1; --l) {
int value = arr[l];
firstOcc.add(l, 1);
if (firstPos[value] != -1) {
firstOcc.add(firstPos[value], -1);
secondOcc.add(firstPos[value], 1);
}
if (secondPos[value] != -1) {
secondOcc.add(secondPos[value], -1);
}
secondPos[value] = firstPos[value];
firstPos[value] = l;
for (const auto& [r, idx] : queriesStartingAt[l]) {
if (answer[idx] != -1) {
continue;
}
int len = r - l + 1;
if (len % 2 == 1) {
answer[idx] = firstOcc.query(r);
} else {
answer[idx] = secondOcc.query(r);
}
}
}
for (int idx = 0; idx < q; ++idx) {
cout << answer[idx] << '\n';
}
return 0;
}
