Cho một dãy số, với mỗi phần tử A của dãy hãy tìm phân tử gần nhất bên phải gọi là phần tử đó B, có số lần suất xuất hiện lớn hơn A. Nếu không tồn tại B thỏa mãn, in ra -1.

Input

Dòng đầu tiên gồm 1 số nguyên t ~(1 \le T \le 100)~, số lượng test.

Mỗi test sẽ gồm 2 dòng :

Dòng đầu tiên gồm 1 số nguyên n ~(1 \le n \le 10^5)~, số lượng phần tử của dãy.

Dòng thứ hai gồm dáy n số nguyên ai ~(1 \le ai \le 10^5)~, với ai là giá trị của phần tử thứ i.

Output

Gồm n số nguyên d1, d2, d3, .. dn, với di là phần tử phải nhất thỏa mãn điều kiện.

Sample Input

3
10
1 3 7 2 5 1 4 2 1 5
5
1 1 1 1 1
6
1 1 2 2 2 3

Sample Output

-1 2 2 1 1 -1 2 1 -1 -1 
-1 -1 -1 -1 -1 
2 2 -1 -1 -1 -1

Nguồn : https://www.hackerearth.com/practice/data-structures/stacks/basics-of-stacks/practice-problems/algorithm/signal-range/