Sau khi xếp chỗ cho mọi người xong, PhuocThien lại nhờ BabyOrange và CandySnowy chút chuyện.
Chuyện là PhuocThien đang làm một chiếc bánh cho bữa tiệc. Tuy nhiên, vì làm quá vội vàng, nên lớp kem trên chiếc bánh không đều nhau. Đều giải quyết vấn đề này, anh ấy quyết định sử dụng một con dao và đặt nó ở một chiều cao nhất định và quét lớp kem từ trái sang phải.
Gọi \({a_i}\) là chiều cao lớp kem ở vị trí \(i\). Giả sử PhuocThien đặt con dao ở chiều cao \(h\). Nếu chiều cao lớp kem ở vị trí \(i\) cao hơn \(h\), toàn bộ lớp kem thừa sẽ bị đẩy xuống vị trí \(i + 1\). Toàn bộ lớp kem thừa tại vị trí \(n\) dẽ bị đẩy hoàn toàn ra khỏi chiếc bánh.
Vì PhuocThien biết các bạn mình rất thích lớp kem trên bánh, nên anh ấy muốn lớp kem trên bánh cao nhất có thể. CandySnowy còn góp ý thêm là nên phục vụ một phần chiếc bánh thay vì cả cái bánh. PhuocThien đồng ý với ý kiến này. Hãy giúp ba bạn tìm chiều cao cao nhất của lớp kem sao cho lớp kem ở \(i\) vị trí đầu tiên đều nhau \((1 \le i \le n)\)

Input

• Dòng đầu tiên in ra số truy vấn \(t\) \((1 \le t \le 10^4)\)
• Mỗi truy vấn có hai dòng:
• Dòng đầu tiên chứa số nguyên \(n\) \(( 2 \le n \le 2 \times 10^5)\)
• Dòng thứ hai chứa \(n\) số nguyên \({a_1}, {a_2}, ..., {a_n}\) \((1 \le {a_i} \le 10^9)\)

Output

• Với mỗi truy vấn in ra \(n\) số nguyên, số thứ \(i\) biểu thị chiều cao cao nhất có thể của lớp kem sao cho lớp kem ở \(i\) vị trí đầu tiên đều nhau.

Example

1
3
4 2 3

4 3 3

4
5
2 3 4 3 2
5
3 3 3 1 1
3
913764826 346182673 764382516
8
6 7 6 7 6 7 6 7

2 2 2 2 2
3 3 3 2 2
913764826 629973749 629973749
6 6 6 6 6 6 6 6