#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include #include #include using namespace std; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i struct S { int sum = 0; int min_cumsum = 0; int max_cumsum = 0; int diff_max = 0; static S plus() { return S{1, 0, 1, 1}; } static S minus() { return S{-1, -1, 0, 0}; } }; S e() { return S(); } S op(S l, S r) { return S{ l.sum + r.sum, std::min(l.min_cumsum, l.sum + r.min_cumsum), std::max(l.max_cumsum, l.sum + r.max_cumsum), std::max({l.diff_max, r.diff_max, l.sum + r.max_cumsum - l.min_cumsum}), }; } int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; vector A(N); for (auto &x : A) cin >> x; vector> query(Q); for (auto &[l, r] : query) cin >> l >> r, --l; vector bin_ng(Q, 0), bin_ok(Q, N); vector> a2is(N + 1), c2qs(N + 1); REP(i, N) a2is.at(A.at(i)).push_back(i); vector init(N, S::plus()); atcoder::segtree tree; while (true) { tree = atcoder::segtree(init); bool flg = false; REP(q, Q) { if (bin_ng.at(q) + 1 < bin_ok.at(q)) { c2qs.at((bin_ng.at(q) + bin_ok.at(q)) / 2).emplace_back(q); flg = true; } } if (!flg) break; int added = 0; REP(c, c2qs.size()) { for (const int q : c2qs.at(c)) { while (added < c) { ++added; for (int i : a2is.at(added)) tree.set(i, S::minus()); } const auto [l, r] = query.at(q); const auto p = tree.prod(l, r); bool success = false; int reduce_plus = 0; if (p.diff_max > 1) reduce_plus = p.diff_max - 1; int cnt_minus = (r - l - p.sum) / 2; int num_plus = r - l - cnt_minus - reduce_plus; if (cnt_minus > num_plus) success = true; (success ? bin_ok : bin_ng).at(q) = c; } c2qs.at(c).clear(); } } for (auto x : bin_ok) cout << x << '\n'; }