六安人论坛招聘网_武汉网站排名提升_今日国内新闻热点_今日油价92汽油价格表

D. 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,\dots ,b_i]$ for all $1\le i\le n$.

However, UFO doesn’t know how to construct array $b$, so you must help her. Note that $1\le b_i\le n$ must hold for your array for all $1\le i\le n$.

Input

The first line contains $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of $a$.

The following line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output $n$ numbers $b_1,b_2,\dots ,b_n$ ($1\le b_i\le 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.

Example

input

4
2
1 2
4
1 1 1 2
8
4 5 5 5 1 1 2 1
10
1 1 2 2 1 1 3 3 1 1

out

1 2
1 1 2 2
4 5 5 1 1 2 2 3
1 8 2 2 1 3 3 9 1 1

Note

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.

题目大意：要构造出一个b数组，令其满足每个a[i] 在[b1,b2,b3,…,bi]中可以做模，那么得到的这个b数组则是正确的。

思路：我们有n个位置放数，那我们就按照123…n这种情况放数，这样每个数只出现一次，这样每一个数都可以作为模数，但是，要注意数出现的顺序，所以我们出现一个新的就输出当前这个数，然后遍历1~n看哪个数还没出现过，没出现的则输出。

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;const int N = 2e5+10;
int a[N];
int vis[N];void solve(){memset(vis,0,sizeof(vis));int n;scanf("%d", &n);for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);if(vis[a[i]] == 0){vis[a[i]] = 1;printf("%d ", a[i]);}}for (int i = 1; i <= n; i++){if(vis[i] == 0){printf("%d ",i);}}return ;
}int main(){int t;scanf("%d", &t);while(t--){solve();}
}