Problem: This is an interactive problem.

We hid from you a permutation p of length n, consisting of the elements from 1 to n. You want to guess it. To do that, you can give us 2 different indices i and j, and we will reply with p_{i} mod p_{j} (remainder of division p_{i} by p_{j}).

We have enough patience to answer at most 2 ⋅ n queries, so you should fit in this constraint. Can you do it?

As a reminder, a permutation of length n is an array consisting of n distinct integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is not a permutation (2 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).

Input

The only line of the input contains a single integer n (1 ≤ n ≤ 10^4) — length of the permutation.

Interaction

The interaction starts with reading n. 

Then you are allowed to make at most 2 ⋅ n queries in the following way: 

  * "? x y" (1 ≤ x, y ≤ n, x ≠ y). 



After each one, you should read an integer k, that equals p_x mod p_y. 

When you have guessed the permutation, print a single line "! " (without quotes), followed by array p and quit.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Exit immediately after receiving "-1" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.

Hack format

In the first line output n (1 ≤ n ≤ 10^4). In the second line print the permutation of n integers p_1, p_2, …, p_n.

Example

Input


3

1

2

1

0

Output


? 1 2

? 3 2

? 1 3

? 2 1

! 1 3 2

Solution (in JAVA):

Solution:


import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.InputMismatchException;
import java.util.TreeMap;

public class Chocolate_bunny {
	static StringBuilder sb;
	static dsu dsu;
	static long fact[];
	static long mod = (int) (1e9);

	static void solve() {
		int n = i();
		int[] ans = new int[n + 1];
		Arrays.fill(ans, -1);
		int mi = 1;
		for (int i = 2; i <= n; i++) {
			System.out.println("? " + " " + mi + " " + i);
			System.out.flush();
			int a = i();

			System.out.println("? " + " " + i + " " + mi);
			System.out.flush();
			int b = i();

			if (a > b) {
				ans[mi] = a;
				mi = i;
			} else {
				ans[i] = b;
			}
		}

		ans[mi] = n;
		sb.append("!");
		for (int i = 1; i <= n; i++) {
			sb.append(" " + ans[i]);
		}
		sb.append("\n");
	}

	public static void main(String[] args) {
		sb = new StringBuilder();
		int test = 1;
//		test = i();
		while (test-- > 0) {
			solve();
		}
		System.out.println(sb);

	}

	/*
	 * fact=new long[(int)1e6+10]; fact[0]=fact[1]=1; for(int i=2;i<fact.length;i++)
	 * { fact[i]=((long)(i%mod)1L(long)(fact[i-1]%mod))%mod; }
	 */
//**************NCR%P******************	 
	static long ncr(int n, int r) {
		if (r > n)
			return (long) 0;

		long res = fact[n] % mod;
		// System.out.println(res);
		res = ((long) (res % mod) * (long) (p(fact[r], mod - 2) % mod)) % mod;
		res = ((long) (res % mod) * (long) (p(fact[n - r], mod - 2) % mod)) % mod;
		// System.out.println(res);
		return res;

	}

	static long p(long x, long y)// POWER FXN //
	{
		if (y == 0)
			return 1;

		long res = 1;
		while (y > 0) {
			if (y % 2 == 1) {
				res = (res * x) % mod;
				y--;
			}

			x = (x * x) % mod;
			y = y / 2;

		}
		return res;
	}

//**************END******************

	// *************Disjoint set
	// union*********//
	static class dsu {
		int parent[];

		dsu(int n) {
			parent = new int[n];
			for (int i = 0; i < n; i++)
				parent[i] = -1;
		}

		int find(int a) {
			if (parent[a] < 0)
				return a;
			else {
				int x = find(parent[a]);
				parent[a] = x;
				return x;
			}
		}

		void merge(int a, int b) {
			a = find(a);
			b = find(b);
			if (a == b)
				return;
			parent[b] = a;
		}
	}

//**************PRIME FACTORIZE **********************************//
	static TreeMap<Integer, Integer> prime(long n) {
		TreeMap<Integer, Integer> h = new TreeMap<>();
		long num = n;
		for (int i = 2; i <= Math.sqrt(num); i++) {
			if (n % i == 0) {
				int nt = 0;
				while (n % i == 0) {
					n = n / i;
					nt++;
				}
				h.put(i, nt);
			}
		}
		if (n != 1)
			h.put((int) n, 1);
		return h;

	}

//****CLASS PAIR ************************************************
	static class Pair implements Comparable<Pair> {
		int x;
		int y;

		Pair(int x, int y) {
			this.x = x;
			this.y = y;
		}

		public int compareTo(Pair o) {
			return (int) (this.y - o.y);

		}

	}
//****CLASS PAIR **************************************************

	static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int Int() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public String String() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public String next() {
			return String();
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}

	static class OutputWriter {
		private final PrintWriter writer;

		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}

		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}

		public void print(Object... objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}

		public void printLine(Object... objects) {
			print(objects);
			writer.println();
		}

		public void close() {
			writer.close();
		}

		public void flush() {
			writer.flush();
		}
	}

	static InputReader in = new InputReader(System.in);
	static OutputWriter out = new OutputWriter(System.out);

	public static long[] sort(long[] a2) {
		int n = a2.length;
		ArrayList<Long> l = new ArrayList<>();
		for (long i : a2)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < l.size(); i++)
			a2[i] = l.get(i);
		return a2;
	}

	public static int[] sort(int[] a2) {
		int n = a2.length;
		ArrayList<Integer> l = new ArrayList<>();
		for (int i : a2)
			l.add(i);
		Collections.sort(l);
		for (int i = 0; i < l.size(); i++)
			a2[i] = l.get(i);
		return a2;
	}

	public static long pow(long x, long y) {
		long res = 1;
		while (y > 0) {
			if (y % 2 != 0) {
				res = (res * x);// % modulus;
				y--;

			}
			x = (x * x);// % modulus;
			y = y / 2;
		}
		return res;
	}

//GCD___+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
	public static long gcd(long x, long y) {
		if (x == 0)
			return y;
		else
			return gcd(y % x, x);
	}
	// ******LOWEST COMMON MULTIPLE
	// *********************************************

	public static long lcm(long x, long y) {
		return (x * (y / gcd(x, y)));
	}

//INPUT PATTERN********************************************************
	public static int i() {
		return in.Int();
	}

	public static long l() {
		String s = in.String();
		return Long.parseLong(s);
	}

	public static String s() {
		return in.String();
	}

	public static int[] readArrayi(int n) {
		int A[] = new int[n];
		for (int i = 0; i < n; i++) {
			A[i] = i();
		}
		return A;
	}

	public static long[] readArray(long n) {
		long A[] = new long[(int) n];
		for (int i = 0; i < n; i++) {
			A[i] = l();
		}
		return A;
	}

}