2044D.md (1978B)
1 Source: https://codeforces.com/problemset/problem/2044/D 2 3 D. Harder Problem 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given a sequence of positive integers, a positive integer is called a mode of the sequence if it occurs the maximum number of times that any positive integer occurs. For example, the mode of $[2,2,3]$ is $2$. Any of $9$, $8$, or $7$ can be considered to be a mode of the sequence $[9,9,8,8,7,7]$. 22 23 You gave UFO an array $a$ of length $n$. To thank you, UFO decides to construct another array $b$ of length $n$ such that $a_i$ is a mode of the sequence $[b_1, b_2, \ldots, b_i]$ for all $1 \leq i \leq n$. 24 25 However, UFO doesn't know how to construct array $b$, so you must help her. Note that $1 \leq b_i \leq n$ must hold for your array for all $1 \leq i \leq n$. 26 27 Input 28 29 The first line contains $t$ ($1 \leq t \leq 10^4$) — the number of test cases. 30 31 The first line of each test case contains an integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the length of $a$. 32 33 The following line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq n$). 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$. 36 37 Output 38 39 For each test case, output $n$ numbers $b_1, b_2, \ldots, b_n$ ($1 \leq b_i \leq n$) on a new line. It can be shown that $b$ can always be constructed. If there are multiple possible arrays, you may print any. 40 41 Example 42 43 Input 44 45 ``` 46 4 47 48 2 49 50 1 2 51 52 4 53 54 1 1 1 2 55 56 8 57 58 4 5 5 5 1 1 2 1 59 60 10 61 62 1 1 2 2 1 1 3 3 1 1 63 ``` 64 65 Output 66 67 ``` 68 1 2 69 1 1 2 2 70 4 5 5 1 1 2 2 3 71 1 8 2 2 1 3 3 9 1 1 72 ``` 73 74 Note 75 76 Let's verify the correctness for our sample output in test case $2$. 77 78 * At $i = 1$, $1$ is the only possible mode of $[1]$. 79 * At $i = 2$, $1$ is the only possible mode of $[1, 1]$. 80 * At $i = 3$, $1$ is the only possible mode of $[1, 1, 2]$. 81 * At $i = 4$, $1$ or $2$ are both modes of $[1, 1, 2, 2]$. Since $a_i = 2$, this array is valid.