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 Main{

   public static void main(String[] args) throws IOException{
       int n = sc.nextInt();

        int[] ans = new int[n];

        if (n == 1) out.println("! 1");
        else{
            // test a0 against every number
            int start = 0;
            int end = 1;
            while(start < n && end < n){
                if (start == end){
                    end++;
                    continue;
                }
                out.println("? " +(start+1) +" " + (end+1));
                out.flush();
                int v1 = sc.nextInt();
                out.println("? " + (end+1) + " " + (start+1));
                out.flush();
                int v2 = sc.nextInt();
                //System.out.println(v1 + " " + v2);
                // whichever one is greater means that one is said number
                if (v1 > v2){
                    // number one is v1
                    ans[start] = v1;
                }
                else{
                    // number i is v2
                    ans[end] = v2;
                }
                while (ans[start] != 0){
                    start++;
                    if (start == n) break;
                }
                while (ans[end] != 0){
                    end++;
                    if (end == n) break;
                }
            }
            int sum = (n) * (n+1)/2;
            int missingIndex = -1;
     for (int i = 0; i < n; i++){
         sum -= ans[i];
         if (ans[i] == 0) missingIndex = i;
        }
        if (missingIndex != -1){
            ans[missingIndex] = sum;
        }
            out.print("! ");
        for (int i = 0; i < n; i++){
            out.print(ans[i] + " ");
        }
        out.println();
        out.flush();
        }
        

out.close();
   }
   
  

   
   
   static class Reader 
   { 
       final private int BUFFER_SIZE = 1 << 16; 
       private DataInputStream din; 
       private byte[] buffer; 
       private int bufferPointer, bytesRead; 

       public Reader() 
       { 
           din = new DataInputStream(System.in); 
           buffer = new byte[BUFFER_SIZE]; 
           bufferPointer = bytesRead = 0; 
       } 

       public Reader(String file_name) throws IOException 
       { 
           din = new DataInputStream(new FileInputStream(file_name)); 
           buffer = new byte[BUFFER_SIZE]; 
           bufferPointer = bytesRead = 0; 
       } 

       public String readLine() throws IOException 
       { 
           byte[] buf = new byte[64]; // line length 
           int cnt = 0, c; 
           while ((c = read()) != -1) 
           { 
               if (c == '\n') 
                   break; 
               buf[cnt++] = (byte) c; 
           } 
           return new String(buf, 0, cnt); 
       } 

       public int nextInt() throws IOException 
       { 
           int ret = 0; 
           byte c = read(); 
           while (c <= ' ') 
               c = read(); 
           boolean neg = (c == '-'); 
           if (neg) 
               c = read(); 
           do
           { 
               ret = ret * 10 + c - '0'; 
           }  while ((c = read()) >= '0' && c <= '9'); 

           if (neg) 
               return -ret; 
           return ret; 
       } 

       public long nextLong() throws IOException 
       { 
           long ret = 0; 
           byte c = read(); 
           while (c <= ' ') 
               c = read(); 
           boolean neg = (c == '-'); 
           if (neg) 
               c = read(); 
           do { 
               ret = ret * 10 + c - '0'; 
           } 
           while ((c = read()) >= '0' && c <= '9'); 
           if (neg) 
               return -ret; 
           return ret; 
       } 

       public double nextDouble() throws IOException 
       { 
           double ret = 0, div = 1; 
           byte c = read(); 
           while (c <= ' ') 
               c = read(); 
           boolean neg = (c == '-'); 
           if (neg) 
               c = read(); 

           do { 
               ret = ret * 10 + c - '0'; 
           } 
           while ((c = read()) >= '0' && c <= '9'); 

           if (c == '.') 
           { 
               while ((c = read()) >= '0' && c <= '9') 
               { 
                   ret += (c - '0') / (div *= 10); 
               } 
           } 

           if (neg) 
               return -ret; 
           return ret; 
       } 

       private void fillBuffer() throws IOException 
       { 
           bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
           if (bytesRead == -1) 
               buffer[0] = -1; 
       } 

       private byte read() throws IOException 
       { 
           if (bufferPointer == bytesRead) 
               fillBuffer(); 
           return buffer[bufferPointer++]; 
       } 

       public void close() throws IOException 
       { 
           if (din == null) 
               return; 
           din.close(); 
       } 
   }

	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	public static Reader sc = new Reader();
}