0と1の境目を探す問題． \(2^{20} > N \) であるから，1回の質問で区間を\(1/2\)にできれば十分．
制約から，0と1の境目がどこかに存在するので，その場所を探す． 今調べている区間を左右2つに分けて，どちらかには境目が存在する．
実際，区間を\(l\cdots r\)の中間を\(m\)とおくと，
- \(l,m\)が同じ値なら区間\(m\cdots r\)の中に境目がある．
- そうでなければ，\(l\cdots m\)の中に境目がある．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
ll l = 0, r = n;
ll s0;
cout << "? " << 1 << endl;
cin >> s0;
while(abs(r-l) > 1){
ll md = (l+r)/2;
cout << "? " << md+1 << endl;
ll x;
cin >> x;
if(s0 == x) l = md;
else r = md;
}
cout << "! " << l+1 << endl;
return 0;
}
