#!/usr/bin/env python3 import sys import random # This uses expected 11/12*n + O(1) ~= 91666+2 queries, which is optimal. # Same algorithm as bergur-better.c: # Query all pairs (2i, 2i+1) # Make a graph with vertices (=values) and edges (=pairs of values queries before). # Find the start of a path of length >= 2 (or an arbitrary point in a cycle if there are no paths). # Query from the first two edges of the path: # - 25% probability of getting a matching pair back -> path shrinks by 2. # - 50% probability that the path reduces length by 1. # - 25% probability that the path reduces by 2, and we have one new extra edge. # # All extra edges can be resolved separately in average O(1) each. n = int(input()) k = n // 2 values = [None] * n # Maps value to list of 2 positions posof = [[] for _ in range(k)] pairedwith = [None] * n perm = list(range(n)) random.shuffle(perm) iperm = [0] * n for i, j in enumerate(perm): iperm[j] = i def query(i, j): print("?", perm[i] + 1, perm[j] + 1, flush=True) a, b = [int(x) - 1 for x in input().split()] set(i, a) set(j, b) return a, b def matchingpos(pos): return sum(posof[values[pos]]) - pos def fix(*ps): for pos in ps: pairedwith[pos] = pos def make_pair(i, j): pairedwith[i] = j pairedwith[j] = i def set(pos, val, remove=True): try: posof[values[pos]].remove(pos) except: pass posof[val].append(pos) values[pos] = val # Solve pair containing i has xy and pair containing j has xy. def xyxy(i2, i, j, j2): x = values[i] y = values[i2] a, b = query(i, j) if a == b: set(i2, x + y - a) set(j2, x + y - b) fix(i, i2, j, j2) return set(i2, a) set(j2, b) xyxy(i, j, i2, j2) # x=y is allowed here def wxyz(i2, i, j, j2): w, x, y, z = values[i2], values[i], values[j], values[j2] if x == y and w == z: return xyxy(i2, i, j, j2) if w == y: i2, i = i, i2 if x == z: j2, j = j, j2 if w == z: i2, i = i, i2 j2, j = j, j2 w, x, y, z = values[i2], values[i], values[j], values[j2] a, b = query(i, j) if a == b: fix(i, j, i2, j2) else: set(i2, w if w not in [a, b] else x) set(j2, z if z not in [a, b] else y) fix(i2, j2) make_pair(i, j) return (i, j) for i in range(0, n, 2): a, b = query(i, i + 1) if a == b: fix(i, i + 1) else: make_pair(i, i + 1) r = None def add_remaining(pr): global r if not r: r = pr return r = wxyz(r[0], r[1], pr[0], pr[1]) # Solve cycle starting at position i2 def solve_cycle(i2): global r while True: i = pairedwith[i2] if i == i2: return if r and i2 in r: return j = matchingpos(i) j2 = pairedwith[j] if r and j in r and j2 in r: r = None w, x, y, z = values[i2], values[i], values[j], values[j2] i2next = matchingpos(i2) if j == j2: add_remaining((i, i2)) return if values[i2] == values[j2]: xyxy(i2, i, j, j2) else: pr = wxyz(i2, i, j, j2) if pr is None: i2 = i2next elif values[pr[0]] == z: i2 = pr[1] elif values[pr[1]] == z: i2 = pr[0] else: add_remaining(pr) i2 = i2next for i in range(n): solve_cycle(i) # Resolve the last remaining if needed if r: xyxy(r[0], r[1], matchingpos(r[1]), matchingpos(r[0])) print("!", *[values[iperm[i]] + 1 for i in range(n)])