(trongcay.*)

Bác Bình có một khu vườn rất nhiều cây, mỗi cây có một chiều cao khác nhau. Bác Bình muốn chọn tất cả các cây đặc biệt trong vườn để trồng thành một hàng cây mới (cây đặc biệt là cây có chiều cao là một số nguyên tố). Hơn nữa để cây tiếp xúc tốt với ánh sáng bác có ý tưởng bố trí các cây đặc biệt theo quy tắc thực hiện lần lượt như sau:

- Bước 1: Chon cây cao nhất đặt làm mốc;

- Bước 2: Cây cao tiếp theo đặt ở bên trái của mốc;

- Bước 3: Câu cao tiếp theo nữa đặt ở bên phải của mốc;

Thực hiện lặp đi lặp lại Bước 2, Bước 3 cho đến khi hết số cây đặc biệt.

Yêu cầu: Cho trước số lượng và chiều cao của các cây trong vườn, hãy giúp bác Bình trồng hàng các cây đặc biệt theo đúng ý tưởng của bác.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên \(n\ (1 < n \leq 10^{6})\) là số lượng cây trong vườn;

+ Dòng thứ hai ghi \(n\) số nguyên \(a_{i}\ (1 \leq a_{i} \leq 10^{7},\ 1 \leq i \leq n)\) là chiều cao của cây thứ \(i\).

Kết quả:

+ Ghi các số trên cùng một dòng là chiều cao của các cây đặc biệt trong hàng cây mới, nếu không có cây đặc biệt nào thì ghi ra giá trị \(- 1\).

Ví dụ:

Giới hạn:

+ Subtask 1: 75% số test có \(1 \leq n \leq 10^{4}\).

+ Subtask 2: 25% số test có \(1 \leq n \leq 10^{6};\)