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


public class C {

    static class Pair<U extends Comparable<U>, V extends Comparable<V>>
            implements Comparable<Pair<U,V>>{

        public final U a;
        public final V b;

        private Pair(U a, V b) {
            this.a = a;
            this.b = b;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;

            Pair<?, ?> pair = (Pair<?, ?>) o;
            if (!a.equals(pair.a))
                return false;
            return b.equals(pair.b);
        }

        @Override
        public int hashCode() {
            return 31 * a.hashCode() + b.hashCode();
        }

        @Override
        public String toString() {
            return "(" + a + ", " + b + ")";
        }

        @Override
        public int compareTo(Pair<U, V> o) {
            if(this.a.equals(o.a)){
                return getV().compareTo(o.getV());
            }
            return getU().compareTo(o.getU());
        }
        private U getU() {
            return a;
        }
        private V getV() {
            return b;
        }
        static void print(Pair[] pairs){
            for(int i=0;i<pairs.length;i++){
                System.out.print(pairs[i]+" ");
            }
            System.out.println();
        }
        static void print(Pair[][] pairs){

            for(int i=0;i<pairs.length;i++){
                for(int j=0;j<pairs[0].length;j++) {
                    System.out.print(pairs[i] + " ");
                }
                System.out.println();
            }
        }
    }


    static BufferedReader inp = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));


    public static void main(String[] args) throws IOException {


        int size = Integer.parseInt(inp.readLine());
        Scanner sc = new Scanner(System.in);
        ArrayList<Pair<Integer,Integer>>[] edge = new ArrayList[size+1];

        int last = 1;
        edge[1] = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();

        if(size==1){
            System.out.println("! 1");
        }
        else {

            for (int i = 1; i < size; i++) {
                edge[i+1] = new ArrayList<>();
                int a = last;
                int b = i + 1;

                System.out.println("?" + " " + last + " " + b);
                System.out.flush();
                int c = sc.nextInt();
                System.out.println("?" + " " + b + " " + last);
                System.out.flush();
                int d = sc.nextInt();

                edge[last].add(new Pair<>(b,d));
                edge[b].add(new Pair<>(last,c));

                if (c > d) {
                    last = i + 1;
                }

            }

//            for(int i=1;i<=size;i++){
//                System.out.println(edge[i]);
//            }

            PriorityQueue<Pair<Integer,Integer>> priorityQueue = new PriorityQueue<>(Comparator.reverseOrder());

            map.put(last,size);
            set.add(last);
            priorityQueue.add(new Pair<>(size,last));



            while (priorityQueue.size()!=0){
                int a = priorityQueue.peek().a;
                int b = priorityQueue.poll().b;
                Iterator<Pair<Integer,Integer>> iterator = edge[b].listIterator();
                while (iterator.hasNext()){
                    Pair<Integer,Integer> pair = iterator.next();
                    if(!set.contains(pair.a)){
                        set.add(pair.a);
                        map.put(pair.a, pair.b);
                        priorityQueue.add(new Pair<>(pair.b, pair.a));
                    }
                }
            }

//
//            System.out.println(map);
//            System.out.println(set);

            out.write("!");
            for (int i = 0; i < size; i++) {
                out.write(" "+map.get(i+1));
            }

            out.flush();
        }


    }




    static void print(int[] array){
        for(int j=0;j<array.length;j++){
            System.out.print(array[j]+" ");
        }
        System.out.println();
    }
    static void print(int[][] array){
        for(int i=0;i< array.length;i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
    static void print(boolean[] array){
        for(int j=0;j<array.length;j++){
            System.out.print(array[j]+" ");
        }
        System.out.println();
    }
    static void print(boolean[][] array){
        for(int i=0;i< array.length;i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
    static void print(long[] array){
        for(int j=0;j<array.length;j++){
            System.out.print(array[j]+" ");
        }
        System.out.println();
    }
    static void print(long[][] array){
        for(int i=0;i< array.length;i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
    static void print(String[] array){
        for(int j=0;j<array.length;j++){
            System.out.print(array[j]+" ");
        }
        System.out.println();
    }
    static void print(String[][] array){
        for(int i=0;i< array.length;i++) {
            for (int j = 0; j < array[0].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }
}