Hôm qua là bữa kiểm tra kiến thức tổng hợp để chuẩn bị đi thi HSG, vì nhận thấy \(Kaninho\) còn yếu về phần mảng, nên hôm nay bố của \(Kaninho\) quyết định ra một bài toán nhằm củng cố kiến thức cho Kaninho như sau:

Cho mảng \(a\) gồm \(n\) phần tử, và chỉ số của mảng bắt đầu từ \(1\).

Yêu cầu: Với mỗi phần tử \(i\) \((1\le i\le n)\) tìm phần tử \(a[j]\) thoả mãn:

• \(1\) < \(i\) < \(j\le n\)

• \(a[i]\) < \(a[j]\)

• \(j\) - \(i\) là nhỏ nhất.

Nếu không tồn tại \(a[j]\) thoả mãn in ra \(-1\)

Input

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

• \(t\) test tiếp theo, mỗi test có dạng như sau:

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

• Dòng thứ hai chứa \(n\) số nguyên \(a_i\) \((1\le a_i\le 50)\)

Output

• Ứng với mỗi testcase, in ra đáp án cần tìm

Scoring

• Subtask \(1\) (\(37.5\%\) số điểm): \(1\le n\le 20\).

• Subtask \(2\) (\(62.5\%\) số điểm): không có điều kiện gì thêm.

Example

2
5
2 3 1 9 4
7
5 7 9 3 2 1 4

3 9 9 -1 -1 
7 9 -1 4 4 4 -1