Cho một mảng a chứa các số được đánh thứ tự từ 1 đến n. Định nghĩa số k của một mảng là số nhỏ nhất xuất hiện trong tất cả mảng con có độ dài k (Mảng con có độ dài k là một phần của mảng a và chứa k phần tử liên tiếp của nó). Nếu không có số nào đều xuất hiện trong mảng con có độ dài k thì số k là -1. Với k từ 1 đến n, tìm số k của mảng a.

Input

• Dòng đầu tiên chứa số test T (1 ≤ T ≤ 50).

• Dòng đầu tiên của mỗi test chứa số n- Độ dài của mảng a (1 ≤ n ≤ ~ 10^3 ~).

• Dòng thứ hai chứa n số nguyên của mảng a : ~ a_1, a_2, a_3, ..., a_n ~ (~ 1 ≤ a_i ≤ n ~)

Output

Với mỗi test case, in ra n số với số thứ i là số i của mảng.

Sample

Input #1

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

Output #1

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

Problem source: Free Contest 126