Problem: Ray lost his array and needs to find it by asking Omkar. Omkar is willing to disclose that the array has the following qualities:

  1. The array has n (1 ≤ n ≤ 2 ⋅ 10^5) elements. 
  2. Every element in the array a_i is an integer in the range 1 ≤ a_i ≤ 10^9. 
  3. The array is sorted in nondecreasing order. 



Ray is allowed to send Omkar a series of queries. A query consists of two integers, l and r such that 1 ≤ l ≤ r ≤ n. Omkar will respond with two integers, x and f. x is the mode of the subarray from index l to index r inclusive. The mode of an array is defined by the number that appears the most frequently. If there are multiple numbers that appear the most number of times, the smallest such number is considered to be the mode. f is the amount of times that x appears in the queried subarray.

The array has k (1 ≤ k ≤ min(25000,n)) distinct elements. However, due to Ray's sins, Omkar will not tell Ray what k is. Ray is allowed to send at most 4k queries.

Help Ray find his lost array.

Input

The only line of the input contains a single integer n (1 ≤ n ≤ 2 ⋅ 10^5), which equals to the length of the array that you are trying to find.

Interaction

The interaction starts with reading n.

Then you can make one type of query:

  * "? \enspace l \enspace r" (1 ≤ l ≤ r ≤ n) where l and r are the bounds of the subarray that you wish to query. 



The answer to each query will be in the form "x \enspace f" where x is the mode of the subarray and f is the number of times x appears in the subarray.

  * x satisfies (1 ≤ x ≤ 10^9). 
  * f satisfies (1 ≤ f ≤ r-l+1). 
  * If you make more than 4k queries or violate the number range in the query, you will get an output "-1." 
  * If you terminate after receiving the response "-1", you will get the "Wrong answer" verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream. 



To output your answer, print:

  * "! \enspace a_1 \enspace a_2 \enspace … \enspace a_{n-1} \enspace a_n" which is an exclamation point followed by the array with a space between every element. 



And quit after that. This query is not counted towards the 4k queries limit.

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.



Hack Format

To hack, output 1 integer on the first line, n (1 ≤ n ≤ 2 ⋅ 10^5). On the second line output n integers a_1, a_2, …, a_{n-1}, a_n separated by a space such that there are at most 25000 distinct numbers and a_j ≤ a_{j+1} for all j from 1 to n-1.

Example

Input


6

2 2

2 2

3 2

2 1


Output


? 1 6

? 1 3

? 4 6

? 3 4

! 1 2 2 3 3 4

Note

The first query is l=1 and r=6. The mode is 2, and 2 appears 2 times, so x=2 and f=2. Note that 3 also appears two times, but 2 is outputted because 2 is smaller.

The second query is l=1 and r=3. The mode is 2 and 2 appears twice in the subarray with indices [1,3].

The third query is l=4 and r=6. The mode is 3 and 3 appears twice in the subarray with indices [4,6].

The fourth query is l=3 and r=4. The mode is 2, which appears once in the subarray with indices [3,4]. Note that 3 also appears once in that range, but 2 is smaller than 3.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.IOException;
import java.util.HashMap;
import java.io.InputStreamReader;
import java.util.Objects;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Queue;
import java.util.ArrayDeque;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author AnandOza
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FOmkarAndModes solver = new FOmkarAndModes();
        solver.solve(1, in, out);
        out.close();
    }

    static class FOmkarAndModes {
        private InputReader in;
        private PrintWriter out;
        private int n;
        private int[] answer;
        HashMap<Pii, Pii> cache = new HashMap<>();

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            this.in = in;
            this.out = out;
            n = in.nextInt();

            answer = new int[n];

            solve(0, n);

            out.println("! " + Util.join(answer));
            out.flush();
        }

        private void solve(int left, int right) {
            if (right - left <= 0)
                return;

            Pii value = query(left, right);
            solve(left, right, value);
        }

        private void solve(int left, int right, Pii mode) {
            if (right - left <= 0)
                return;

            int x = mode.first, f = mode.second;

            if (f == 1) {
                answer[left] = x;
                for (int i = left + 1; i < right; i++) {
                    answer[i] = query(i);
                }
                return;
            }

            if (f == right - left) {
                for (int i = left; i < right; i++) {
                    answer[i] = x;
                }
                return;
            }

            Queue<Pair<Pii, Pii>> q = new ArrayDeque<>();
            int start = -1, end = -1;
            for (int i = left; i < right; i += f) {
                int boxStart = i;
                int boxEnd = Math.min(right, i + f);
                if (end != -1)
                    boxStart = Math.max(boxStart, end);
                if (boxEnd <= boxStart)
                    continue;

                Pii interval = query(boxStart, boxEnd);

                if (interval.first == x) {
                    int count = interval.second;

                    if (count == f) {
                        start = boxStart;
                        end = boxEnd;
                    } else if (query(boxStart - 1) == x) {
                        end = boxStart + count;
                        start = end - f;
                    } else if (query(boxEnd) == x) {
                        start = boxEnd - count;
                        end = start + f;
                    }

                    for (int j = start; j < end; j++) {
                        answer[j] = x;
                    }

                    solve(boxStart, start);
                    solve(end, boxEnd);
                } else {
                    q.add(Pair.of(Pii.of(boxStart, boxEnd), interval));
                }
            }
            for (Pair<Pii, Pii> item : q) {
                int l = item.first.first, r = item.first.second;
                Pii interval = item.second;

                if (l <= start && start < r) {
                    r = start;
                }
                if (l <= end && end < r) {
                    l = end;
                }
                solve(l, r, interval);
            }
        }

        private int query(int i) {
            if (i < 0 || i >= n)
                return -1;

            return query(i, i + 1).first;
        }

        private Pii query(int l, int r) {
            Pii key = Pii.of(l, r);
            if (cache.containsKey(key))
                return cache.get(key);

            out.println("? " + (l + 1) + " " + r);
            out.flush();
            int x = in.nextInt(), f = in.nextInt();
            Pii value = Pii.of(x, f);
            cache.put(key, value);
            return value;
        }

    }

    static class Pair<F, S> {
        public final F first;
        public final S second;

        public Pair(F first, S second) {
            this.first = first;
            this.second = second;
        }

        public static <F, S> Pair<F, S> of(F first, S second) {
            return new Pair<>(first, second);
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pair<?, ?> pair = (Pair<?, ?>) o;
            return Objects.equals(first, pair.first) && Objects.equals(second, pair.second);
        }

        public int hashCode() {
            return Objects.hash(first, second);
        }

        public String toString() {
            return "(" + first + ", " + second + ')';
        }

    }

    static class Util {
        public static String join(int... i) {
            StringBuilder sb = new StringBuilder();
            for (int o : i) {
                sb.append(o);
                sb.append(" ");
            }
            if (sb.length() > 0) {
                sb.deleteCharAt(sb.length() - 1);
            }
            return sb.toString();
        }

        private Util() {
        }

    }

    static class InputReader {
        public final BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }

    static class Pii implements Comparable<Pii> {
        public final int first;
        public final int second;

        public Pii(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public static Pii of(int first, int second) {
            return new Pii(first, second);
        }

        public boolean equals(Object o) {
            if (this == o)
                return true;
            if (o == null || getClass() != o.getClass())
                return false;
            Pii pair = (Pii) o;
            return first == pair.first && second == pair.second;
        }

        public int hashCode() {
            return Arrays.hashCode(new int[]{first, second});
        }

        public String toString() {
            return "(" + first + ", " + second + ')';
        }

        public int compareTo(Pii o) {
            if (first != o.first)
                return Integer.compare(first, o.first);
            return Integer.compare(second, o.second);
        }

    }
}