• Cho mảng \(a\) gồm \(n\) số nguyên dương

• Gọi \(q_k\) là số nguyên nhỏ nhất có mặt ở tất cả các đoạn con (gồm các phần tử liên tiếp) có kích thước là \(k\).

• Nếu không tồn tại \(q_k\) thỏa mãn điều trên thì \(q_k=-1\).

Nhiệm vụ của chúng ta là in ra tất cả các giá trị \(q_i\) với \(1\le i\le n\).

Input

• Dòng thứ nhất chứa số nguyên \(t(1\le t\le 1000)\) - Thể hiện số lượng testcase

• Tiếp theo là \(t\) block, mỗi block có dạng như sau:

• Dòng thứ nhất chứa số nguyên \(n(1\le n\le 3.10^5)\)

• Dòng thứ hai chứa số nguyên \(a_1,a_2,...,a_n\) với \(1\le a_i\le n\)

  (Biết rằng: Tổng các giá trị của \(n\) ở tất cả testcase không quá \(3.10^5\))

Output

• ứng với mỗi testcase ,in ra các giá trị \(q_1,q_2,...,q_n\) tương ứng

Example

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

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