Tâm có $n$ thanh gỗ có dạng khối trụ tròn xoay, với chiều cao là số nguyên. Một thanh gỗ mà độ dài của nó có đúng 3 ước dương thì được Tâm gọi là một thanh hoa. Từ $n$ thanh gỗ, Tâm lấy ra tất cả các thanh hoa, dựng chúng đứng thành một hàng, tạo thành một hình mà Tâm gọi là phong đỉnh (phong ở đây có nghĩa là mũi nhọn, giống như trong tiên phong hay động Phong Nha), theo cách:

• Bước 1: Dựng thanh hoa cao nhất đứng làm mốc.
• Bước $2k$: Dựng thanh hoa cao nhất (trong những thanh hoa chưa dựng) đứng ngoài cùng bên trái.
• Bước $2k+1$: Dựng thanh hoa cao nhất (trong những thanh hoa chưa dựng) đứng ngoài cùng bên phải.

($k$ nguyên dương)

Yêu cầu

Cho chiều cao của $n$ thanh gỗ, hãy cho biết chiều cao của các thanh hoa trong phong đỉnh, theo thứ tự từ trái qua phải.

Dữ liệu

Vào từ đầu vào chuẩn

• Dòng đầu tiên chứa số nguyên dương $n$.
• Dòng tiếp theo chứa $n$ số nguyên dương $a_1,a_2,\ldots,a_n$ là chiều cao của $n$ thanh gỗ.

Kết quả

Ghi ra đầu ra chuẩn nhiều số nguyên lần lượt là chiều cao của các thanh hoa trong phong đỉnh, theo thứ tự từ trái qua phải.

Ví dụ mẫu

7
2510 4 1 3011 3481 4 361

4 361 3481 4

Giới hạn

Subtask 1 (25% số điểm): $n\le{10}^4;a_i\le{10}^4$.

Subtask 2 (30% số điểm): $n\le{10}^4;a_i\le{10}^8$.

Subtask 3 (25% số điểm): $n\le{10}^6;a_i\le{10}^8$.

Subtask 4 (20% số điểm): $n\le{10}^6;a_i\le{10}^9$.