#include using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define trav(a, x) for(auto& a : x) #define all(x) x.begin(), x.end() #define sz(x) (int)(x).size() typedef long long ll; typedef pair pii; typedef vector vi; const int MAXN = 100000; struct qpair{ int ai, aj, i, j; bool operator==(qpair& p2){ return tie(ai, aj, i, j) == tie(p2.ai, p2.aj, p2.i, p2.j); } }; bool comp(qpair p1, qpair p2){ return min(p1.ai, p1.aj) < min(p2.ai, p2.aj); } int n; bool frozen[MAXN] = {0}; int A[MAXN] = {0}; vector pairs; vector pairs2; pii ask(int i, int j){ cout << "? " << i+1 << " " << j+1 << "\n"; fflush(stdout); pii res; cin >> res.first >> res.second; return res; } void freeze(int i, int x){ A[i] = x; frozen[i] = 1; } int other(qpair p, int x, int y){ if(min(x,y) == min(p.ai,p.aj) && max(x,y) == max(p.ai,p.aj))return -1; if(x == y){ if(p.ai != x)return p.ai; return p.aj; } if(x != p.ai && x != p.aj){ if(y == p.ai)return p.aj; return p.ai; } if(x == p.ai)return p.aj; return p.ai; } int lucky = 0; int normal = 0; int unlucky = 0; vector > edge_pairs; set endpoints, doubles, loners; void reclassify(int x){ endpoints.erase(x); doubles.erase(x); loners.erase(x); if(sz(edge_pairs[x]) == 0)return; // isolated if(sz(edge_pairs[x]) == 2){ doubles.insert(x); return; } int y = edge_pairs[x][0].aj; if(y == x)y = edge_pairs[x][0].ai; if(sz(edge_pairs[y]) == 1){ loners.insert(x); return; } endpoints.insert(x); } void reset_all(int x){ reclassify(x); trav(q, edge_pairs[x]){ reclassify(q.ai); reclassify(q.aj); } } void remove(qpair p){ if(!(edge_pairs[p.ai].back() == p))swap(edge_pairs[p.ai][0], edge_pairs[p.ai][1]); if(!(edge_pairs[p.aj].back() == p))swap(edge_pairs[p.aj][0], edge_pairs[p.aj][1]); edge_pairs[p.ai].pop_back(); edge_pairs[p.aj].pop_back(); reset_all(p.ai); reset_all(p.aj); } void add(qpair p){ edge_pairs[p.ai].push_back(p); edge_pairs[p.aj].push_back(p); reset_all(p.ai); reset_all(p.aj); } void ask_pair(qpair p1, qpair p2){ remove(p1); remove(p2); pii res = ask(p1.i, p2.i); int x = res.first; int y = res.second; int other1 = other(p1, x, y); int other2 = other(p2, x, y); if(other1 == -1){ other1 = p2.ai; if(p2.ai == other2)other1 = p2.aj; } if(other2 == -1){ other2 = p1.ai; if(p1.ai == other1)other2 = p1.aj; } if(x == y){ freeze(p1.i, x); freeze(p2.i, x); freeze(p1.j, other1); freeze(p2.j, other2); } else{ if(min(p1.ai, p1.aj) != min(p2.ai, p2.aj) || max(p1.ai, p1.aj) != max(p2.ai, p2.aj)){ freeze(p1.j, other1); freeze(p2.j, other2); frozen[p1.i] = 0; frozen[p2.i] = 0; add({x, y, p1.i, p2.i}); } else{ add({x, y, p1.i, p2.i}); add({x, y, p1.j, p2.j}); } } } void end_game(qpair p){ if(p.ai == p.aj){ freeze(p.i, p.ai); freeze(p.j, p.aj); } else{ for(int k = 0; k < n; k++){ if(A[k] == p.ai && k != p.i && k != p.j){ vi ind = {k, p.i, p.j}; while(1){ int a = rand()%2; int b = a + rand()%2 + 1; if(b == 3)b--; pii q = ask(ind[a], ind[b]); if(q.first == q.second){ int c = 0; if(a == c)c = 1; if(b == c)c = 2; freeze(ind[a], p.ai); freeze(ind[b], p.ai); freeze(ind[c], p.aj); return; } } } } } } int main() { cin >> n; rep(c1,0,n+1){ vector temp; edge_pairs.push_back(temp); } for(int c1 = 0; c1 < n; c1 += 2){ pii p = ask(c1,c1+1); int a = p.first; int b = p.second; if(a == b){ freeze(c1, a); freeze(c1+1, a); } else{ add({a, b, c1, c1+1}); } } for(int c1 = 0; c1 < n+1; c1++){ reclassify(c1); } while(sz(doubles) + sz(loners) + sz(endpoints) > 2){ if(sz(endpoints) > 0){ int x = *endpoints.begin(); int y = edge_pairs[x][0].ai; if(y == x)y = edge_pairs[x][0].aj; ask_pair(edge_pairs[y][0], edge_pairs[y][1]); continue; } if(sz(doubles) > 0){ int y = *doubles.begin(); ask_pair(edge_pairs[y][0], edge_pairs[y][1]); continue; } auto it = loners.begin(); vi L; for(int c1 = 0; c1 < 3; c1++){ L.push_back(*it); it++; } if(edge_pairs[L[0]][0] == edge_pairs[L[1]][0]){ ask_pair(edge_pairs[L[0]][0], edge_pairs[L[2]][0]); } else{ ask_pair(edge_pairs[L[0]][0], edge_pairs[L[1]][0]); } } while(sz(doubles) > 0){ int y = *doubles.begin(); ask_pair(edge_pairs[y][0], edge_pairs[y][1]); } if(sz(loners) > 0){ int last = *loners.begin(); end_game(edge_pairs[last][0]); } cout << "! "; for(int c1 = 0; c1 < n; c1++){ cout << A[c1] << " "; }cout << "\n"; return 0; }