Tý tham dự ngày hội thể thao, \(n\) vận động viên xếp thành một hàng dọc. Mỗi người có chiều cao \(h_i\).

Một vận động viên ở vị trí \(i\) có thể nhìn thấy vận động viên đầu tiên bên phải mình cao hơn mình. Nếu không ai cao hơn, họ nhìn thấy bầu trời (in ra \(-1\)).

Hãy tìm next greater element cho mỗi vị trí.

Gợi ý: Dùng stack đơn điệu — duyệt từ phải sang trái, giữ stack giảm dần.

Ràng buộc

Input

Dòng đầu chứa \(n\) (\(1 \le n \le 10^5\)). Dòng hai chứa \(n\) số \(h_i\) (\(1 \le h_i \le 10^9\)).

Output

In ra \(n\) số — chiều cao của người cao hơn đầu tiên bên phải (hoặc \(-1\)).

Example

6
4 3 8 2 5 1

Output:

8 8 -1 5 -1 -1

Giải thích: Người ở vị trí 1 (cao 4) nhìn thấy người 3 (cao 8). Người ở vị trí 2 (cao 3) cũng thấy người 8. Người vị trí 3 (cao 8) không ai cao hơn.