CF2044D Harder Problem

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

The first line contains $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains an integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of $ a $ . The following line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

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.

Let's verify the correctness for our sample output in test case $ 2 $ . - At $ i = 1 $ , $ 1 $ is the only possible mode of $ [1] $ . - At $ i = 2 $ , $ 1 $ is the only possible mode of $ [1, 1] $ . - At $ i = 3 $ , $ 1 $ is the only possible mode of $ [1, 1, 2] $ . - At $ i = 4 $ , $ 1 $ or $ 2 $ are both modes of $ [1, 1, 2, 2] $ . Since $ a_i = 2 $ , this array is valid.