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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class C{
    public static FastReader fs = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    
    static int ask(int i,int j) {
    	out.println('?' + " " + i + " " + j);
    	out.flush();
    	return fs.nextInt();
    }
    
    static void solve() {
        int n = fs.nextInt();
        TreeSet<Integer> st = new TreeSet<>(),st1 = new TreeSet<>();
        for(int i = 0; i<n; i++) {
        	st.add(i+1);
        	st1.add(i+1);
        }
        int[] ans = new int [n+1];
        while(st.size()>1) {
        	int x = st.first();
        	st.remove(st.first());
        	int y = st.first();
        	st.remove(st.first());
        	int ans1 = ask(x,y);
        	int ans2 = ask(y,x);
        	if(ans1 > ans2) {
        		ans[x] = ans1;
        		st.add(y);
        		st1.remove(ans1);
        	}
        	else {
        		ans[y] = ans2;
        		st.add(x);
        		st1.remove(ans2);
        	}
        }
        int left = st.first();
        ans[left] = st1.first();
        out.print("! ");
        for(int i = 1; i<=n; i++) {
        	out.print(ans[i] + " ");
        }
        out.println();
    }
    
    public static void main(String[] args) {
        Thread t = new Thread(null,null,"",1 << 28) {
            public void run() {
                int test_case = 1;
                //test_case = fs.nextInt();
                for(int cs = 1; cs <= test_case; cs++) {
                    solve();
                }
                out.close();
            }
        };
        t.start();
        try {
            t.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
        
        int [] readintarray(int n) {
            int res [] = new int [n];
            for(int i = 0; i<n; i++)res[i] = nextInt();
            return res;
        }
        long [] readlongarray(int n) {
            long res [] = new long [n];
            for(int i = 0; i<n; i++)res[i] = nextLong();
            return res;
        }
    } 
    
    static int ceil(int x,int y) {
        return (x % y == 0 ? x / y : (x / y +1));
    }
    
    static long ceil(long x,long y) {
        return (x % y == 0 ? x / y : (x / y +1));
    }
    
    static <T extends Comparable<T>> T min(T x, T y) {
        if(x.compareTo(y) <= 0)
            return x;
        return y;
    }

    static <T extends Comparable<T>> T max(T x, T y) {
        if(x.compareTo(y) >= 0)
            return x;
        return y;
    }

    static <T extends Comparable<T>> T max(T[] a){
        T res = a[0];
        for(int i = 1; i<a.length; i++){
            if(res.compareTo(a[i]) >= 0){
                res = a[i];
            }
        }
        return res;
    }

    static <T extends Comparable<T>> T min(T[] a){
        T res = a[0];
        for(int i = 1; i<a.length; i++){
            if(res.compareTo(a[i]) <= 0){
                res = a[i];
            }
        }
        return res;
    }

    static int power(int x,int y) {
        int res = 1;
        while(y > 0) {
            if( y % 2 == 1)res = (res * x);
            y >>= 1;
            x = (x * x);
        }
        return res;
    }
    
    static long power(long x,long y) {
        long res = 1;
        while(y > 0) {
            if( y % 2 == 1)res = (res * x);
            y >>= 1;
            x = (x * x);
        }
        return res;
    }
    
    static long power(long x,long y,long mod) {
        long res = 1;
        x %= mod;
        while(y > 0) {
            if( y % 2 == 1)res = (res * x) % mod;
            y >>= 1;
            x = (x * x) % mod;
        }
        return res;
    }

    static <T extends Comparable<T>> void Sort(T[] a){
        ArrayList<T> temp = new ArrayList<>();
        for(int i = 0; i<a.length; i++)temp.add(a[i]);
        Collections.sort(temp);
        for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
    }
    
    static <T extends Comparable<T>> void Rsort(T[] a){
        ArrayList<T> temp = new ArrayList<>();
        for(int i = 0; i<a.length; i++)temp.add(a[i]);
        Collections.sort(temp);
        Collections.reverse(temp);
        for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
    }

    static <T extends Comparable<T>> void intervalsort(T a [],int start,int end) {
        ArrayList<T> temp = new ArrayList<>();
        for(int i = start; i<end; i++)
            temp.add(a[i]);
        Collections.sort(temp);
        for(int i = 0; i<temp.size(); i++)
            a[i+start] = temp.get(i);
    }
}