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.*;
public class MyClass {
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; 
        } 
    } 
    static int gcd(int a, int b) 
    { 
        // Everything divides 0  
        if (a == 0) 
          return b; 
        if (b == 0) 
          return a; 
       
        // base case 
        if (a == b) 
            return a; 
       
        // a is greater 
        if (a > b) 
            return gcd(a-b, b); 
        return gcd(a, b-a); 
    }
    static int ask(int a,int b)
    {
        FastReader s=new FastReader();
        System.out.println("? "+(a+1)+" "+(b+1));
        System.out.flush();
        int z=s.nextInt();
        
        return z;
    }
    public static void main(String args[]) 
{
	FastReader s=new FastReader();
	
	int t=0,n=0,max=0,mx=0,pos=0,gcd1=0,gcd2=0;
	
	
	n=s.nextInt();
	
	//int mx=0;
	int ans[]=new int[n];
	Arrays.fill(ans,-1);
     //Scanner in=new Scanner(System.in);
     //if(in.hasNext())
     //t=s.nextInt();
     mx=0;
     for(int i=1;i<n;i++)
     {
         gcd1=ask(mx,i);
         gcd2=ask(i,mx);
         if(gcd1>gcd2)
         {
             ans[mx]=gcd1;
             mx=i;
         }
         else
         {
             ans[i]=gcd2;
         }
     }
     ans[mx]=n;
      //   if(in.hasNext())
         //n=s.nextInt();
         //int a[]=new int[n];
         System.out.flush();
         System.out.println("! ");
         for(int i=0;i<n;i++)
         {
             System.out.print(ans[i]+" ");
         }
         System.out.println();
         /*Arrays.sort(a);
         int buff[]=new int[a.length];
         gcd1=a[a.length-1];
         System.out.print(gcd1+" ");
         buff[a.length-1]=1;
         for(int i=a.length-1;i>=0;i--)
         {
             gcd2=gcd1;
             //if(buff[i]==0)
             //{System.out.print(a[i]+" ");buff[i]=1;}
             max=0;
             pos=-1;
             for(int j=a.length-1;j>=0;j--)
             {
                 if(buff[j]==0)
                 {
                     ans=gcd(gcd2,a[j]);
                     //System.out.println("gcd2="+gcd2+" a[j]="+a[j]+" ans="+ans);
                     if(ans>max)
                     {
                         max=ans;
                         pos=j;
                     }
                 }
             }
             //System.out.println("so ans="+max);
             if(pos!=-1)
             {buff[pos]=1;System.out.print(a[pos]+" ");gcd1=max;}
             else
             break;
         }
         System.out.println();
     }*/
    }
}