Trong ván bài đỏ đen, khả năng thao túng quân bài là kỹ năng bá đạo và hiệu quả nhất để thay đổi vận mệnh.

Sau khi chơi thua hết xèng, Loli cực kỳ cay cú. Tuy nhiên, cô ta vẫn ở lại và chú ý xem xét và phân tích cách chia bài cũng như cách đặt bài trong mỗi một ván bài của các cao thủ võ lâm. Dường như không có sự ngẫu nhiên nào ở đây cả, cũng như chẳng có may rủi. Tất cả đều đã được tính toán.

Trong một ván bài, Loli sẽ phải solo với một đối thủ khác trong bàn. Mỗi người được đưa một bộ bài có ~n~ lá và mỗi lá bài có giá trị là một số nguyên dương, các lá đều có giá trị đôi một khác nhau.

Ban đầu, người chơi được đặt sẵn thứ tự của các lá bài trong bộ bài theo thứ tự mà người đó muốn. Sau đó tên xào bài luôn xào và phát bài cho người chơi theo cách thức sau:

• Tất cả quân bài ban đầu đều được úp xuống.
• Tên xào bài sẽ đưa cho người chơi lá ở trên cùng bộ bài (lá đầu tiên).
• Tiếp theo, hắn sẽ đặt lá ở trên cùng bộ bài lúc này xuống cuối cùng (sau lá cuối cùng).

Quá trình này lặp đi lặp lại cho đến khi bộ bài không còn bài. Người chơi sẽ tìm một dãy tăng dần liên tiếp xuất hiện trong bộ bài của mình. Sau đó dùng dãy đó để đọ với người kia, người nào có dãy dài hơn sẽ giành chiến thắng.

Loli phát hiện ra phương pháp xào bài lỏ này và muốn bạn tìm cách "thao túng" bộ bài trước khi bị xào, sao cho cổ luôn có được dãy tăng dần dài nhất có thể, để giành được chiến thắng và trả nợ hoàn lương.

Input

• Dòng đầu chứa số nguyên dương ~n\ (n \le 10^5)~,
• Dòng thứ 2 chứa ~n~ số nguyên dương ~a_i\ (a_i \le 10^9)~ là giá trị của mỗi quân bài.

Output

• ~n~ số nguyên dương là thứ tự dãy bài trước khi đưa cho tên xào bài, sao cho sau khi xào bài, ta có được dãy tăng dần liên tiếp dài nhất có thể.

Subtasks

• Subtask 1: ~20\%~ test có ~n \le 10~;
• Subtask 2: ~20\%~ test có ~n \le 100,\ a_i \le 10^4~;
• Subtask 3: ~20\%~ test có ~n \le 5000,\ a_i \le 10^4~;
• Subtask 4: ~20\%~ test có ~n \le 5000,\ a_i \le 10^9~;
• Subtask 5: ~20\%~ test không có ràng buộc gì thêm.

Sample Input 1

4
7 9 6 5

Sample Output 1

5 7 6 9

Sample Input 2

7
15 14 13 2 6 7 8

Sample Output 2

2 14 6 13 7 15 8

Giải thích:

Ở test đầu tiên, ta có dãy bài ban đầu là ~[7,9,6,5]~, đáp án là ~[5,7,6,9]~. Ta sẽ kiểm tra đáp án:

• Bộ bài hiện là ~[5,7,6,9]~.
• Đưa cho người chơi lá ~5~, cho lá ~7~ xuống cuối. Bộ bài hiện là ~[6,9,7]~.
• Đưa cho người chơi lá ~6~, cho lá ~9~ xuống cuối. Bộ bài hiện là ~[7,9]~.
• Đưa cho người chơi lá ~7~, cho lá ~9~ xuống cuối. Bộ bài hiện là ~[9]~.
• Đưa cho người chơi lá ~9~.

Dễ thấy, người chơi được nhận dãy bài ~[5,6,7,9]~, là dãy tăng dần liên tiếp dài nhất có thể.