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:
//   package com.company;

  import java.util.*;
  import java.io.*;
  import java.lang.*;

  public class Main{

      public static void main(String args[]){
          PrintWriter out=new PrintWriter(System.out);
          InputReader in=new InputReader(System.in);
          TASK solver = new TASK();
//          int t = in.nextInt();
        int t=1;
          /*
           ** @author Jigar_Nainuji
           ** SVNIT-SURAT
           */
          for(int i=0;i<t;i++)
          {
              solver.solve(in,out,i);
          }
          out.close();
      }
      static class TASK {
          static int mod = 1000000007;

          void solve(InputReader in, PrintWriter out, int testNumber) {
             int n = in.nextInt();
             int a[] = new int[n+1];
             Set<Integer> s = new HashSet<>();
             Stack<Integer> stack = new Stack<>();
             for(int i=n;i>=3;i--)
                 stack.push(i);
             int i1=1,i2=2;

             while(s.size()!=n-1)
             {
                 System.out.println("? "+i1+" "+i2);
                 int a1 = in.nextInt();
                 System.out.println("? "+i2+" "+i1);
                 int a2=in.nextInt();
                 if(a2<a1)
                 {
                     a[i1]=a1;
                     s.add(a1);
                     if(!stack.empty())
                        i1=stack.pop();
                 }
                 else
                 {
                     a[i2]=a2;
                     s.add(a2);
                     if(!stack.empty())
                     i2=stack.pop();
                 }

             }
              System.out.print("! ");
             for(int i=1;i<=n;i++)
             {
                 if(a[i]==0)
                 {
                     for(int j=1;j<=n;j++)
                     {
                         if(s.contains(j))
                             continue;
                         else
                         {
                             a[i]=j;
                             break;
                         }
                     }
                 }
                 System.out.print(a[i]+" ");
             }
              System.out.flush();



          }
      }

      static class pair{
          int x;
          int y;
          pair(int x,int y)
          {
              this.x=x;
              this.y=y;
          }

      }
      static class Maths{
          static int gcd(int a, int b) {
              if (a == 0)
                  return b;
              return gcd(b % a, a);
          }



          public static long factorial(int n){
              long fact = 1;
              for(int i=1;i<=n;i++){
                  fact *= i;
              }
              return fact;
          }
      }


      static class InputReader {
          private InputStream stream;
          private byte[] buf = new byte[1024];
          private int curChar;
          private int numChars;
          private SpaceCharFilter filter;

          public InputReader(InputStream stream) {
              this.stream = stream;
          }

          public int read() {
              if (numChars == -1)
                  throw new InputMismatchException();

              if (curChar >= numChars) {
                  curChar = 0;
                  try {
                      numChars = stream.read(buf);
                  } catch (IOException e) {
                      throw new InputMismatchException();
                  }

                  if (numChars <= 0)
                      return -1;
              }
              return buf[curChar++];
          }

          public String nextLine() {
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              String str = "";
              try {
                  str = br.readLine();
              } catch (IOException e) {
                  e.printStackTrace();
              }
              return str;
          }

          public int nextInt() {
              int c = read();

              while (isSpaceChar(c))
                  c = read();

              int sgn = 1;

              if (c == '-') {
                  sgn = -1;
                  c = read();
              }

              int res = 0;
              do {
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              }
              while (!isSpaceChar(c));

              return res * sgn;
          }

          public long nextLong() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              long res = 0;

              do {
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              }
              while (!isSpaceChar(c));
              return res * sgn;
          }

          public double nextDouble() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              int sgn = 1;
              if (c == '-') {
                  sgn = -1;
                  c = read();
              }
              double res = 0;
              while (!isSpaceChar(c) && c != '.') {
                  if (c == 'e' || c == 'E')
                      return res * Math.pow(10, nextInt());
                  if (c < '0' || c > '9')
                      throw new InputMismatchException();
                  res *= 10;
                  res += c - '0';
                  c = read();
              }
              if (c == '.') {
                  c = read();
                  double m = 1;
                  while (!isSpaceChar(c)) {
                      if (c == 'e' || c == 'E')
                          return res * Math.pow(10, nextInt());
                      if (c < '0' || c > '9')
                          throw new InputMismatchException();
                      m /= 10;
                      res += (c - '0') * m;
                      c = read();
                  }
              }
              return res * sgn;
          }

          public String readString() {
              int c = read();
              while (isSpaceChar(c))
                  c = read();
              StringBuilder res = new StringBuilder();
              do {
                  res.appendCodePoint(c);
                  c = read();
              }
              while (!isSpaceChar(c));

              return res.toString();
          }

          public boolean isSpaceChar(int c) {
              if (filter != null)
                  return filter.isSpaceChar(c);
              return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
          }

          public String next() {
              return readString();
          }

          public interface SpaceCharFilter {
              public boolean isSpaceChar(int ch);
          }
      }
  }