#include <bits/stdc++.h> #define int long long using namespace std; const long long N = 2e5 + 5; int a[N]; int n; bool chk(int l, int r) { if (r >= n) return 0; else if (l < 0) return 0; bool ans; cout << "? " << l + 1 << " " << r + 1 << endl; cin >> ans; return ans; } int bin(int L, int R) { if (!chk(L, R)) return 0; int l = 0, r = min(n - r, l) + 2; while (r - l > 1) { int mid = (r + l) / 2; chk(L - mid, R + mid) ? (l = mid) : (r = mid); } return R + l + 1 - (L - l); } void solve() { cin >> n; int ans = 1; for (int i = 0; i < n; i++) { // cout << " i = " << i << endl; // single character is middle // at least ans of them should make a palindrome // cout << " odd ------------------" << endl; // if (previous palindrom was even length) lets say 4 length, now we need a 5 length one, so 2 + middle + 2 if (ans % 2 == 0) { ans = max(ans, bin(i - ans / 2, i + ans / 2)); } // if (previous palindrom was odd length) lets say 5 length, now we need a 7 length one, so 3 + middle + 3 else { ans = max(ans, bin(i - (ans + 1) / 2, i + (ans + 1) / 2)); } // cout << " even ------------------" << endl; // two in middle // at least ans of them should make a palindrome // if (previous palindrom was even length) lets say 8 length, now we need a 10 length one, so 4 + middle +(middle+1) + 4 if (ans % 2 == 0) ans = max(ans, bin(i - ans / 2, i + ans / 2 + 1)); // if (previous palindrom was odd length) lets say 1 length, now we need a 2 length one, so 0 + middle + (middle+1) + 00 else ans = max(ans, bin(i - ans / 2, i + ans / 2 + 1)); } cout << ans << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); int t = 1; // cin >> t; for (int i = 1; i <= t; i++) { // cout << "Case #" << i << ':' << ' '; solve(); cout << endl; } return 0; }