1416_A. k-Amazing Numbers
You 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 ≤ t ≤ 1000) — the number of test cases. Then t test cases follow.

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

It is guaranteed that the sum of n over all test cases does not exceed 3 ⋅ 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 
```python
t = int(input())

ns = []

for i in range(t):

    n = int(input())
    arr = list(map(int, input().split()))

    nums = set(arr)
    dct1 = {}
    dct2 = {num: 0 for num in nums}

    for idx, el in enumerate(arr):
        if el in dct1:
            dct2[el] = max(dct2[el], idx - dct1[el])
        else:
            dct2[el] = idx + 1
        dct1[el] = idx

    for el in dct2:
        dct2[el] = max(dct2[el], n - dct1[el])

    ans = []
    temp = sorted(nums, key=lambda x: dct2[x])
    index = 0

    mini = 10**20
    for k in range(1, n + 1):
        while index < len(temp) and dct2[temp[index]] == k:
            mini = min(mini, temp[index])
            index += 1       
        if mini == 10**20:
            ans.append(-1)
        else:
            ans.append(mini)

    ns.append(ans)


for el in ns:
    print(" ".join(list(map(str, el))))

```