Bạn được cho một dãy số nguyên độ dài $n$: $a_1, a_2, \dots, a_n$.

Xét tất cả $n$ phép dịch vòng (xoay vòng) có thể có của dãy này. Với một vị trí bắt đầu $p$ ($1 \le p \le n$), phép dịch vòng tương ứng là dãy

$$b_1, b_2, \dots, b_n = a_p, a_{p+1}, \dots, a_n, a_1, a_2, \dots, a_{p-1}.$$

Đối với dãy đã dịch chuyển này, định nghĩa dãy giá trị lớn nhất tiền tố $c_1, c_2, \dots, c_n$ của nó bởi

$$c_i = \max(b_1, b_2, \dots, b_i) \quad \forall i = 1, 2, \dots, n.$$

Chúng ta so sánh hai dãy có cùng độ dài bằng thứ tự từ điển thông thường: $c$ nhỏ hơn $d$ theo thứ tự từ điển khi và chỉ khi tồn tại một chỉ số $i$ sao cho $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ và $c_i < d_i$.

Nhiệm vụ của bạn là chọn một phép dịch vòng của dãy ban đầu sao cho dãy giá trị lớn nhất tiền tố của nó có thứ tự từ điển nhỏ nhất trong số tất cả $n$ phép dịch vòng có thể có.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên duy nhất $T$ ($1 \le T \le 2 \cdot 10^5$), số lượng bộ kiểm tra.

Mỗi bộ kiểm tra gồm hai dòng:

• Dòng đầu tiên chứa một số nguyên duy nhất $n$ ($1 \le n \le 5 \cdot 10^5$).
• Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Dữ liệu đảm bảo rằng tổng của $n$ trên tất cả các bộ kiểm tra không vượt quá $5 \cdot 10^5$.

Kết quả

Với mỗi bộ kiểm tra, in ra một dòng chứa $n$ số nguyên: dãy giá trị lớn nhất tiền tố có thứ tự từ điển nhỏ nhất sau khi dịch vòng.

Ví dụ

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

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