【競プロ典型 90 問】 053 - Discrete Dowsing（★7） https://atcoder.jp/contests/typical90/tasks/typical90_ba

053.cpp

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

#define MT make_tuple

void solve() {
	int n; cin >> n;
	
	vector<int> memo(n + 1, -1);
	auto val = [&](int i) {
		assert(1 <= i);
		if(i <= n) {
			if(memo[i] == -1) {
				cout << "? " << i << endl;
				cin >> memo[i];
			}
			return memo[i];
		} else {
			return n - i;
		}
	};
	
	int L = 0, m1 = 987, H = 1597;
	while(true) {
		int m2 = L + (H - m1);
		if(m1 == m2) { break; }
		if(m1 >  m2) { swap(m1, m2); }
		tie(L, m1, H) = (val(m1) > val(m2) ? MT(L, m1, m2) : MT(m1, m2, H));
	}
	cout << "! " << val(m1) << endl;
}

int main() {
	int t; cin >> t;
	for(int i = 0; i < t; i++) { solve(); }
}