L. Good Sets
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an array $$$a$$$ of size n. We call a set of indices $$$b_1, b_2, b_3, ..., b_m$$$ good if it satisfies $$$$$$b_1+1 \lt b_2, \space b_2+1 \lt b_3, \space b_3+1 \lt b_4, \space ...., \space b_{m-1}+1 \lt b_m $$$$$$ and so on. And the score of this good set is: $$$$$$max(a_{b_1}, \space a_{b_2}, \space a_{b_3}, \space ..., \space a_{b_m})$$$$$$ For each integer $$$ i \space (1 \le i \le n)$$$ output the minimum score of a good set of size $$$i$$$ or $$$-1$$$ if there are no good sets.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$, the number of test cases.

Each test case contains two lines: In the first line, there is a single integer $$$n$$$ $$$(1 \le n \le 10^6)$$$, the size of the array. In the second line, there are $$$n$$$ integers $$$a_1, a_2, a_3, ..., a_n (1 \le a_i \le 10^9)$$$, the elements of the array. It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$10^6$$$.

Output

For each test case, output n integers, the minimum score of a good set of size $$$i (1 \le i \le n)$$$ or $$$-1$$$ if there are no good sets.

Example
Input
5
1
5
2
4 3
6
2 3 7 2 1 5
8
1 2 1 2 1 2 1 2
5
100000 1000000 10000000 100000000 1000000000
Output
5 
3 -1 
1 2 5 -1 -1 -1 
1 1 1 1 -1 -1 -1 -1 
100000 10000000 1000000000 -1 -1