#include #include #include #include #define MAXN 100000 #define rep(E, F) for (E = 0; E < (F); E++) int min(int a, int b) { if (a > b) return b; return a; } int max(int a, int b) { if (a < b) return b; return a; } int get_int() { int r = 0, c = getchar(), s = (c == ' ' ? -1 : 1); if (c < '0' || c > '9') return get_int(); for (; c >= '0' && c <= '9'; c = getchar()) r = r*10 + c - '0'; return s*r; } void swap(int* a, int* b) { int s = *a; *a = *b; *b = s; } void shuffle(int* a, int n) { for (int i = 0, j, s; i < n; i++) { j = rand()%(n - i); swap(&a[j], &a[n - 1 - i]); } } typedef struct par{ int x, y, z, w;} par; par topar(int x, int y, int z, int w) { par r = {x, y, z, w}; return r; } int cmp(const void *p1, const void *p2) { return ((par*)p1)->x - ((par*)p2)->x; } int n, b[MAXN], g[MAXN], f[MAXN], perm[MAXN]; void query(int x, int y, int *xx, int *yy) { printf("? %d %d\n", x + 1, y + 1); fflush(stdout); *xx = get_int(), *yy = get_int(); } void fix(int i, int x) { b[i] = x, g[i] = 1, f[x]++; } par s[MAXN]; int ss = 0; int t1, t2, t3; void step1(par p1, par p2) { int x, y; if (p1.x > p1.y) swap(&p1.x, &p1.y); if (p2.x > p2.y) swap(&p2.x, &p2.y); if (p1.x == p2.x && p1.y == p2.y) { t1++; while (1) { query(p1.z, p2.z, &x, &y); if (x == y) { fix(p1.z, x); fix(p2.z, x); fix(p1.w, p1.x + p1.y - x); fix(p2.w, p1.x + p1.y - x); return; } query(p1.z, p1.w, &x, &y); if (x == y) { fix(p1.z, x); fix(p1.w, x); fix(p2.z, p1.x + p1.y - x); fix(p2.w, p1.x + p1.y - x); return; } } } if (p1.x == p2.y) swap(&p2.x, &p2.y); if (p1.y == p2.x) swap(&p1.x, &p1.y); if (p1.y == p2.y) swap(&p1.x, &p1.y), swap(&p2.x, &p2.y); if (p1.x == p2.x) { t2++; query(p1.z, p2.z, &x, &y); if (x == y) { fix(p1.z, x); fix(p2.z, x); assert(p1.x + p1.y - x > 0); fix(p1.w, p1.x + p1.y - x); assert(p2.x + p2.y - x > 0); fix(p2.w, p2.x + p2.y - x); } else { if (x == p2.y || y == p1.y) swap(&x, &y); assert(p1.x + p1.y - x > 0); fix(p1.w, p1.x + p1.y - x); assert(p2.x + p2.y - y > 0); fix(p2.w, p2.x + p2.y - y); s[ss++] = topar(x, y, p1.z, p2.z); } return; } t3++; query(p1.z, p2.z, &x, &y); if (x != p1.x && x != p1.y) swap(&x, &y); fix(p1.w, p1.x + p1.y - x); fix(p2.w, p2.x + p2.y - y); s[ss++] = topar(x, y, p1.z, p2.z); return; } void step3(par p) { int i, x, y; rep(i, n) if (b[i] == p.x && i != p.z && i != p.w) break; while (1) { query(i, p.z, &x, &y); if (x == y) { fix(p.z, x); fix(p.w, p.x + p.y - x); break; } query(p.w, p.z, &x, &y); if (x == y) { fix(p.z, x); fix(p.w, x); fix(i, p.x + p.y - x); break; } } } int main() { int i, j, x, y, aa = 0; rep(i, n) f[i] = g[i] = 0; n = get_int(); par a[n]; rep(i, n) perm[i] = i; shuffle(perm, n); rep(i, n/2) { query(perm[i*2], perm[2*i + 1], &x, &y); if (x == y) fix(perm[2*i], x), fix(perm[2*i + 1], y); else a[aa++] = topar(x, y, perm[2*i], perm[2*i + 1]); } t1 = t2 = t3 = 0; while (aa > 1) { rep(i, aa) if (f[a[i].y] == 0) swap(&a[i].x, &a[i].y); qsort(a, aa, sizeof(a[0]), cmp); rep(i, aa/2) step1(a[2*i], a[2*i + 1]); if(aa%2 == 1) s[ss++] = a[aa - 1]; rep(i, ss) a[i] = s[i]; aa = ss, ss = 0; } fprintf(stderr, ">> t1, t2, t3 = %d, %d, %d\n\n", t1, t2, t3); if (aa != 0) step3(a[0]); printf("!"); rep(i, n) printf(" %d", b[i]); printf("\n"); return 0; }