#include using namespace std; int n, qc = 0; bool simulate = false; vector sim; pair query(int i, int j) { qc++; cout << "? " << i+1 << " " << j+1 << endl; if (simulate) { int a = sim[i], b = sim[j]; if (rand()%2) swap(sim[i],sim[j]); if (rand()%2) swap(a,b); return {a,b}; } else { int a, b; cin >> a >> b; return {a-1,b-1}; } } void check(vector res) { cout << "!"; for (int x: res) cout << " " << x+1; cout << endl; if (simulate) { assert(res == sim); } } int main() { cin >> n; srand(time(0)); if (n < 0) { n = abs(n); simulate = true; sim.resize(n); for (int i = 0; i < n; i++) sim[i] = i/2; random_shuffle(begin(sim), end(sim)); } int perm[n]; for (int i = 0; i < n; i++) perm[i] = i; random_shuffle(perm, perm + n); vector>> adj(n/2); set Q; auto add_edge = [&](int a, int b, int i, int j) { if (i > j) swap(i,j); adj[a].emplace(b,i,j); adj[b].emplace(a,i,j); if (int(adj[a].size()) == 2) Q.insert(a); if (int(adj[b].size()) == 2) Q.insert(b); }; vector res(n,-1); for (int i = 0; i < n; i += 2) { auto [a,b] = query(perm[i],perm[i+1]); if (a == b) res[perm[i]] = res[perm[i+1]] = a; else add_edge(a,b,perm[i],perm[i+1]); } while (!Q.empty()) { int a = *begin(Q); Q.erase(a); assert(int(adj[a].size()) == 2); int b, c, i, j, k, l; tie(b,i,j) = *begin(adj[a]); tie(c,k,l) = *rbegin(adj[a]); adj[a].clear(); adj[b].erase({a,i,j}); adj[c].erase({a,k,l}); Q.erase(b), Q.erase(c); if (b == c) { auto [u,v] = query(i,k); if (u == v) { res[i] = res[k] = u; res[j] = res[l] = u^a^b; } else { add_edge(a,b,i,k); add_edge(a,b,j,l); } } else { auto [u,v] = query(i,k); if (u == v) { res[i] = res[k] = a; res[j] = b, res[l] = c; } else { if (u != a) swap(u,v); if (u == a) { if (v == b) { res[j] = a, res[l] = c; add_edge(a,b,i,k); } else { res[j] = b, res[l] = a; add_edge(a,c,i,k); } } else { res[j] = res[l] = a; add_edge(b,c,i,k); } } } } for (int a = 0; a < n/2; a++) { if (!adj[a].empty()) { int b = get<0>(*begin(adj[a])); if (a < b) Q.insert(a); } } while (int(Q.size()) > 1) { int a = *begin(Q); Q.erase(a); int c = *begin(Q); Q.erase(c); int b, d, i, j, k, l; tie(b,i,j) = *begin(adj[a]); tie(d,k,l) = *begin(adj[c]); adj[a].clear(), adj[b].clear(); adj[c].clear(), adj[d].clear(); auto [u,v] = query(i,k); if (u != a && u != b) swap(u,v); if (u != a) swap(a,b); if (v != c) swap(c,d); assert(u == a && v == c); add_edge(a,c,i,k); Q.insert(a); res[j] = b, res[l] = d; } if (!Q.empty()) { int a = *begin(Q); int b, i, j; tie(b,i,j) = *begin(adj[a]); int k = 0; while (res[k] != a) k++; while (true) { auto [u,v] = query(i,k); if (u == v) { res[i] = res[k] = a; res[j] = b; break; } else { swap(j,k); } } } check(res); cerr << qc << endl; }