CF1372F.Omkar and Modes

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.

Ray 丢失了他的数组，需要通过向 Omkar 提问来找回它。Omkar 愿意透露该数组具有以下性质：

1. 数组包含 $n$（$1 \le n \le 2 \cdot 10^5$）个元素。
2. 数组中每个元素 $a_i$ 均为整数，且满足 $1 \le a_i \le 10^9$。
3. 数组按非递减顺序排列。

Ray 可以向 Omkar 发送一系列查询。每次查询由两个整数 $l$ 和 $r$ 构成，满足 $1 \le l \le r \le n$。Omkar 将返回两个整数 $x$ 和 $f$：

• $x$ 是子数组 $a[l..r]$（即从下标 $l$ 到 $r$ 的闭区间子数组）的众数（mode）。数组的众数定义为出现次数最多的数；若存在多个出现次数最多的数，则取其中最小的那个数作为众数。
• $f$ 是 $x$ 在所查询子数组中出现的次数。

该数组共有 $k$（$1 \le k \le \min(25000,n)$）个互不相同的元素。然而，由于 Ray 的过错，Omkar 不会告诉 Ray $k$ 的值。Ray 最多可发送 $4k$ 次查询。

请帮助 Ray 找回他丢失的数组。

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.

输入仅包含一行，其中有一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示你试图构造的数组的长度。

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

第一个查询的 $l=1$ 且 $r=6$。众数为 $2$，而 $2$ 出现了 $2$ 次，因此 $x=2$ 且 $f=2$。注意，$3$ 也出现了 $2$ 次，但输出的是 $2$，因为 $2 < 3$。

第二个查询的 $l=1$ 且 $r=3$。众数为 $2$，且 $2$ 在下标范围 $[1,3]$ 的子数组中出现了两次。

第三个查询的 $l=4$ 且 $r=6$。众数为 $3$，且 $3$ 在下标范围 $[4,6]$ 的子数组中出现了两次。

第四个查询的 $l=3$ 且 $r=4$。众数为 $2$，它在下标范围 $[3,4]$ 的子数组中出现了一次。注意，$3$ 在该范围内也出现了一次，但 $2 < 3$。