Omkar and Modes
Contest: Codeforces Round 655 (Div. 2)
Difficulty rating: 2700
Tags: binary search, divide and conquer, interactive

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 \le n \le 2 \cdot 10^5$$$) elements.
2. Every element in the array $$$a_i$$$ is an integer in the range $$$1 \le a_i \le 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 \le l \le r \le 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 \le k \le \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 format:
The only line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), which equals to the length of the array that you are trying to find.

Interaction format:
The interaction starts with reading $$$n$$$.

Then you can make one type of query:

- "$$$? \enspace l \enspace r$$$" ($$$1 \le l \le r \le 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 \leq x \leq 10^9$$$).
- $$$f$$$ satisfies ($$$1 \leq f \leq 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 \ldots \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 \le n \le 2 \cdot 10^5$$$). On the second line output $$$n$$$ integers $$$a_1, a_2, \ldots, a_{n-1}, a_n$$$ separated by a space such that there are at most $$$25000$$$ distinct numbers and $$$a_j \le a_{j+1}$$$ for all $$$j$$$ from $$$1$$$ to $$$n-1$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
6

2 2

2 2

3 2

2 1

Example output:
? 1 6

? 1 3

? 4 6

? 3 4

! 1 2 2 3 3 4

Editorial:
For both solutions, we must first make the critical observation that because the array is sorted, all occurrences of a value $$$x$$$ occur as a single contiguous block.
Solution 1
We will define a recursive function $$$determine(l, r)$$$ which will use queries to determine the array. We will also store an auxiliary list of previously returned query values $$$(x, f)$$$ – not the queries themselves, but only the values returned, so that we know that if $$$(x, f)$$$ is in the list then some previous query revealed that there were $$$f$$$ instances of $$$x$$$ in some query, and that we haven't already determined exactly where in the array those $$$f$$$ instances of $$$x$$$ are.
The execution of $$$determine(l, r)$$$ will proceed as follows: first, query the interval $$$[l, r]$$$, and let the result be $$$(x_1, f_1)$$$.
If there exists some previous query result $$$(x_1, f_2)$$$ in our auxiliary list, then we will guarantee by details yet to be explained of $$$determine(l, r)$$$ that the interval that produced that result contained $$$[l, r]$$$ and that no part of those $$$f_2$$$ occurrences of $$$x_1$$$ occurred to the left of $$$[l, r]$$$. This allows us to exactly determine the location of those $$$f_2$$$ occurrences of $$$x_1$$$. We mark these occurrences in our answer, and then remove $$$(x_1, f_2)$$$ from our auxiliary list and do not add $$$(x_1, f_1)$$$. If $$$[l, r]$$$ is not entirely composed of occurrences of $$$x_1$$$, then the remaineder of the interval must be $$$[l, r']$$$ for some $$$r'$$$, and in that case we then call $$$determine(l, r')$$$.
If there does not exist some previous query result $$$(x_1, f_2)$$$ in our auxiliary list, then we add $$$(x_1, f_1)$$$ to the list and do as follows: while the exact locations of those $$$f_1$$$ occurrences of $$$x_1$$$ have not been determined, call $$$determine(l', l' + f_1 - 1)$$$, where $$$l'$$$ is the leftmost index in $$$[l, r]$$$ which has not yet been determined. Once those locations have been determined, call $$$determine(l', r)$$$.
To determine the entire array we simply call $$$determine(1, n)$$$. It is clear that this will correctly determine the array. We can see that it uses at most $$$4k$$$ queries as follows: for each block of integers of the same value represented by a query result $$$(x, f)$$$ that we add to our auxiliary list, we use $$$2$$$ queries to determine the exact location of those integers: one when added $$$(x, f)$$$ to the list, and one when removing $$$(x, f)$$$ from the list.
This does not guarantee that the algorithm uses $$$2k$$$ queries because some calls of $$$determine$$$ can split a block of integers of the same value into two blocks. However, we can show that any blocks formed by splitting a single block into two cannot be further split as they occur either at the beginning or end of a queried interval (the full proof is left as an exercise to the reader), so each distinct value in the array will produce at most $$$2$$$ blocks, each of which will be determined in $$$2$$$ queries, meaning that the algorithm uses at most $$$4k$$$ queries.
Side note: you can in fact further show that the algorithm always uses at most $$$4k - 4$$$ queries and that there exists an array for all $$$k \geq 2$$$ which forces the algorithm to use $$$4k - 4$$$ queries.
Solution 2
Again, we will define a recursive function $$$determine(l, r)$$$, but this time we will only additionally maintain the currently known values in the answer.
The execution of $$$determine(l, r)$$$ will proceed as follows: first, query the interval $$$[l, r]$$$ and let the result be $$$(x, f)$$$. Then, find the largest integer $$$k$$$ such that $$$2^k \leq f$$$ and then for all $$$j$$$ in $$$[l, r]$$$ that are multiples of $$$2^k$$$, determine the value located at index $$$j$$$, either by querying $$$[j, j]$$$ or by using already known values.
By the definition of $$$k$$$, there will be either one or two such indexes $$$j$$$ such that the values at those indexes are equal to $$$x$$$.
If there is only one such index, let this index be $$$j_1$$$. Make two queries $$$[j_1 - 2^k + 1, j_1]$$$ and $$$[j_1, j_1 + 2^k - 1]$$$ and let the results of these queries be $$$(x_1, f_1)$$$ and $$$(x_2, f_2)$$$ respectively. We can show that at least one of $$$x_1$$$ and $$$x_2$$$ must be equal to $$$x$$$. If $$$x_1 = x$$$, then we see that the $$$f$$$ occurrences of $$$x$$$ must be precisely the interval $$$[j_1 - f_1 + 1, j_1 - f_1 + f]$$$. If $$$x_2 = x$$$, then we see that the $$$f$$$ occurrences of $$$x$$$ must be precisely the interval $$$[j_1 + f_2 - f, j_1 + f_2 - 1]$$$.
If there are two such indexes, let these indexes be $$$j_1$$$ and $$$j_2$$$ so that $$$j_1 < j_2$$$. Note that it must be true that $$$j_1 + 2^k = j_2$$$. Make a single query $$$[j_1 - 2^k + 1, j_2]$$$ and let the result be $$$(x_1, f_1)$$$. We can show that $$$x_1$$$ must be equal to $$$x$$$, so we can then conclude that the $$$f$$$ occurrences fo $$$x$$$ must be precisely the interval $$$[j_2 - f_1 + 1, j_2 - f_1 + f]$$$.
After the interval containing the $$$f$$$ occurrences of $$$x$$$ has been determined, mark these occurrences in our answer and then call $$$determine$$$ on the remaining not-fully-determined interval to the left if it exists and the remaining not-fully-determined interval to the right if it exists.
To determine the entire array we simply call $$$determine(1, n)$$$. It is clear that this will correctly determine the array. We can see that it uses at most $$$4k$$$ queries as follows: Each call to $$$determine$$$ finds all occurrences of a distinct value $$$x$$$. We will refer to the queries of single indexes $$$j$$$ that were multiples of some $$$2^k$$$ as $$$j$$$-queries. For each $$$x$$$, we perform the following queries other than $$$j$$$-queries: the first query in $$$determine$$$, and then either two additional queries if only one $$$j$$$-query was found to equal $$$x$$$, or a single additional query if two $$$j$$$-queries were found to equal $$$x$$$. This means that if we group each $$$j$$$-query with the value $$$x$$$ that it equaled, then we will have performed exactly $$$4$$$ queries for each $$$x$$$, and so the algorithm must therefore use exactly $$$4k$$$ queries.