#include #define rep(i, n) for (int i = 0; i < (n); i++) #define repr(i, n) for (int i = (n) - 1; i >= 0; i--) using namespace std; using ll = long long; int cnt; #ifdef DEBUG int a[300]; bool lt(int x, int y) { cnt++; return a[x] > a[y]; } #else bool lt(int x, int y) { cnt++; cout << "? " << x+1 << ' ' << y+1 << endl; int res; cin >> res; return res == y+1 ? 1 : 0; } #endif int main() { // cin.tie(nullptr); // ios::sync_with_stdio(false); mt19937 mt(123); #ifdef DEBUG rep(i, 300) a[i] = i; int n = 300; #else int n; cin >> n; #endif vector ord(n); rep(i, n) ord[i] = i; for (int i = 0; i < n; i++) { int r = uniform_int_distribution(0, i)(mt); swap(ord[i], ord[r]); } int first, second; if (lt(ord[0], ord[1])) { first = ord[1]; second = ord[0]; } else { first = ord[0]; second = ord[1]; } for (int i = 2; i < n; i++) { if (lt(ord[i], second)) { } else if (lt(ord[i], first)) { second = ord[i]; } else { second = first; first = ord[i]; } } cout << "! " << second+1 << endl; cerr << cnt << endl; }