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.util.*;
import java.io.*;
import java.util.Map.Entry;


public class Main{

	static final int inf=Integer.MAX_VALUE;
	static int mod=(int)1e9+7;
	static long [] fact;
	
	
	//divide into cases, brute force
	//sort, greedy, binary search
	//transform into graph
	
	static void solve(Reader in, Writer out){
		
		int n=in.ni();
		int largest=1;
		int permutation[]=new int[n];
		for(int i=2; i<=n; ++i){
			int r1=query(largest,i,in), r2=query(i,largest,in);
			if(r1>r2){
				permutation[largest-1]=r1;
				largest=i;
			}else{
				permutation[i-1]=r2;
			}
		}		
		permutation[largest-1]=n;
		out.print("! ");
		out.println(permutation);

	}

	static int query(int i, int j, Reader in){
		System.out.println("? "+i+" "+j);
		System.out.flush();
		int q=in.ni();
		return q;
	}

	public static void main(String[] args) throws IOException {
		Writer out=new Writer(System.out);
		Reader in=new Reader(System.in);	
		// mod=998244353;
		int ts=1;
		// ts=in.ni();
		while(ts-->0) {
			solve(in, out);
		}
		out.close();
	}
	static long ppow(long n, long m){
		if(m==0) return 1;
		long tmp=ppow(n,m/2);
		tmp=tmp*tmp%mod;
		return m%2==0 ? tmp : tmp*n %mod;
	}
	static long gcd(long n, long m){ return m==0 ? n : gcd(m, n%m); }
	static long lcm(long n, long m){ return n/gcd(n,m)*m; }
	static long nCr(int n, int r){ return fact[n]*ppow(fact[n-r], mod-2) % mod * ppow(fact[r],mod-2) % mod; }
	static void factInit(int n){ fact=new long[n]; fact[0]=1; for(int i=1; i<n; ++i) fact[i]=fact[i-1]*i % mod; }
	static int smaller(long [] a, long k){
		if(a[0]>k) return 0; int t=0;
		for(int j=a.length; j>=1; j/=2){ while(t+j<a.length && a[t+j]<k) t+=j; } return t+1;
	}
	static void reverse(int a[]){
		ArrayList<Integer> al=new ArrayList<>();
		for(int i: a) al.add(i); Collections.reverse(al);
		for(int i=0; i<al.size(); ++i) a[i]=al.get(i); 
	}
	static void reverse(long a[]){
		ArrayList<Long> al=new ArrayList<>();
		for(long i: a) al.add(i); Collections.reverse(al);
		for(int i=0; i<al.size(); ++i) a[i]=al.get(i); 
	}
	static void sort(int a[]) {
		ArrayList<Integer> al=new ArrayList<>();
		for(int i: a) al.add(i); Collections.sort(al);
		for(int i=0; i<a.length; ++i) a[i]=al.get(i);
	}
	static void sort(long a[]){
		ArrayList<Long> al=new ArrayList<>();
		for(long i: a) al.add(i); Collections.sort(al);
		for(int i=0; i<a.length; ++i) a[i]=al.get(i);
	}
	static void sort(pair [] p){
		ArrayList<pair> pl=new ArrayList<>(); for(pair pa: p) pl.add(pa);
		Collections.sort(pl, (p1, p2)->{
			return Long.compare(p1.u, p2.u)==0 ? Long.compare(p1.v,p2.v): Long.compare(p1.u,p2.u);
		});
		for(int i=0; i<p.length; ++i) p[i]=pl.get(i);
	}
	static void reverse(pair[] p){
		int n=p.length;
		for(int i=0; i<p.length/2; ++i){
			pair tmp=new pair(0,0); tmp.copy(p[i]);
			p[i].copy(p[n-1-i]); p[n-1-i].copy(tmp);
		}
	}
	static class pair{
		long u,v; pair(long g, long h){u=g; v=h;}
		void copy(pair p){u=p.u; v=p.v;};
	}
	static class Reader{	
		BufferedReader br;
		StringTokenizer to;
		Reader(InputStream stream){
			br=new BufferedReader(new InputStreamReader(stream));
			to=new StringTokenizer("");
		}
		String nextLine() {
			String line="";
			try { line=br.readLine(); }catch(IOException e) {};
			return line;
		}
		String ns() {
			while(!to.hasMoreTokens()) { try { to=new StringTokenizer(br.readLine()); }catch(IOException e) {} }
			return to.nextToken();
		}
		int ni() { return Integer.parseInt(ns()); }
		long nl() { return Long.parseLong(ns()); }
		int [] ra(int n) { int a[]=new int[n]; for(int i=0; i<n; i++) a[i]=ni(); return a; }
		long [] rla(int n) { long [] a =new long[n]; for(int i=0; i<n; ++i) a[i]=nl(); return a; }
	}	
	static class Writer extends PrintWriter{
		Writer(OutputStream stream){ super(stream); }
		void println(pair p){ println(p.u+" "+p.v); }
		void println(int a[]){ for(int i: a) print(i+" "); println(); }
	}
}