Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
A. k-Amazing Numbers

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou are given an array $$$a$$$ consisting of $$$n$$$ integers numbered from $$$1$$$ to $$$n$$$.

Let's define the $$$k$$$-amazing number of the array as the minimum number that occurs in all of the subsegments of the array having length $$$k$$$ (recall that a subsegment of $$$a$$$ of length $$$k$$$ is a contiguous part of $$$a$$$ containing exactly $$$k$$$ elements). If there is no integer occuring in all subsegments of length $$$k$$$ for some value of $$$k$$$, then the $$$k$$$-amazing number is $$$-1$$$.

For each $$$k$$$ from $$$1$$$ to $$$n$$$ calculate the $$$k$$$-amazing number of the array $$$a$$$.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of elements in the array. The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of the array.

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

Output

For each test case print $$$n$$$ integers, where the $$$i$$$-th integer is equal to the $$$i$$$-amazing number of the array.

Example

Input

3 5 1 2 3 4 5 5 4 4 4 4 2 6 1 3 1 5 3 1

Output

-1 -1 3 2 1 -1 4 4 4 2 -1 -1 1 1 1 1

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/06/2021 21:27:47 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|