Lagu

Untuk mengisi acara penutupan OSN 2009, Pak Dengklek sudah menciptakan dan mencatat sebuah lagu spesial. Masalahnya, beberapa hari menjelang acara tersebut, catatan berisi urutan not-not lagu Pak Dengklek hilang. Ia hanya ingat bahwa semua not pada lagunya adalah unik. Tidak ada satu pun not yang sama digunakan lebih dari satu kali dalam lagunya. Tentunya dibutuhkan waktu yang tidak sebentar untuk mengingat-ingat dan mengurutkan kembali not-not lagunya seperti rencana semula. Mengingat waktu yang sempit, Pak Dengklek akhirnya mengambil jalan pintas untuk mengurutkan not-not tersebut. Ia hanya ingin not-not lagunya membentuk urutan zig zag. Zig zag di sini berarti untuk setiap not X, not yang dimainkan tepat sebelum dan tepat sesudah not X harus sama-sama lebih besar dari not X atau sama-sama lebih kecil dari not X. Dengan kata lain, not di posisi ke-(i-1) dan ke-(i+1), keduanya harus sama-sama lebih besar dari not di posisi ke-i atau sama-sama lebih kecil dari not di posisi ke-i. Pengecualian diberikan kepada not pertama dan terakhir karena hanya terdapat satu not yang tepat bersebelahan dengannya. Gambar di bawah ini memberikan contoh urutan zig zag yang dimaksud.

Cara yang relatif mudah ini ternyata cukup sulit juga jika diaplikasikan untuk not dalam jumlah yang besar. Oleh karena itu Pak Dengklek meminta bantuan Anda. Pak Dengklek juga sadar bahwa dengan cara ini mungkin terdapat lebih dari satu urutan yang valid, tapi dalam kepanikannya Pak Dengklek tidak begitu peduli lagi, ia sudah cukup senang jika Anda dapat memberikan salah satu dari banyak kemungkinan tersebut.

FORMAT MASUKAN

Baris pertama berisi sebuah bilangan bulat N (1 ≤ N ≤ 100 000) yang menyatakan banyaknya not yang harus diurutkan secara zig-zag. N baris berikutnya berisi bilangan-bilangan yang mewakili not-not tersebut. Semua bilangan yang diberikan adalah bilangan positif yang lebih kecil dari 1 000 000.

FORMAT KELUARAN

N baris, masing-masing berisi sebuah bilangan yang mewakili not-not yang sudah diurutkan secara zig-zag. Seperti dijelaskan pada deskripsi soal, jika terdapat lebih dari satu kemungkinan, cukup cetak salah satu saja.

CONTOH MASUKAN

8
6
1
2
3
4
10
8
5

CONTOH KELUARAN

3
2
4
1
10
6
8
5

Penjelasan Contoh

Contoh keluaran di atas adalah salah satu dari banyak kemungkinan jawaban. Contoh keluaran tersebut sesuai dengan gambar yang diberikan pada deskripsi soal.