Stack dan Queue

Dalam dunia informatika, penggunaan struktur data queue (antrian) dan stack (tumpukan) sangatlah umum. Kedua struktur data tersebut memiliki kesamaan yakni bahwa keduanya dapat diimplementasikan menggunakan array. Sedangkan perbedaannya terletak pada cara keluar masuk elemen. Struktur data queue memiliki sifat FIFO (first in, first out), artinya elemen yang pertama kali masuk juga akan keluar pertama kali. Sedangkan struktur data stack memiliki sifat LIFO (last in, first out), artinya elemen yang terakhir kali masuk akan keluar pertama kali juga.
Pak Dengklek meminta Anda untuk mensimulasikan sebuah struktur data yang merupakan gabungan antara queue dan stack. Pada struktur data ini, suatu elemen dapat masuk ke bagian awal menggunakan perintah push_front maupun bagian akhir menggunakan perintah push_back. Begitu juga proses pengambilan elemen, dapat mengambil dari bagian awal menggunakan perintah pop_front maupun dari bagian akhir menggunakan perintah pop_back. Diberikan struktur data tersebut dalam keadaan kosong, lakukan N (1 ≤ N ≤ 10.000) operasi memasukkan dan mengeluarkan elemen, dan tentukan kondisi akhir dari struktur data tersebut.

Format Masukan

Baris pertama berisi sebuah bilangan bulat N. N baris berikutnya masing-masing berisi sebuah perintah. Sesuai deskripsi di atas, terdapat 4 kemungkinan perintah yaitu:

• push_front, memasukkan elemen ke bagian awal struktur data
• push_back, memasukkan elemen ke bagian akhir struktur data
• pop_front, mengeluarkan sebuah elemen dari bagian awal struktur data
• pop_back, mengeluarkan sebuah elemen dari bagian akhir struktur data

Perintah push_front dan push_back tentunya akan diikuti sebuah elemen berupa bilangan bulat antara 1 sampai 1.000.000. Dan perintah pop_front maupun pop_back tidak akan dilakukan saat struktur data tersebut tidak memiliki elemen.

Format Keluaran

Baris-baris sebanyak jumlah elemen pada kondisi akhir struktur data tersebut. Baris-baris tersebut berisi elemen-elemen berurutan dari bagian awal sampai bagian akhir yang berada di kondisi akhir struktur data tersebut.

Contoh Masukan

7
push_back 1
push_back 2
push_front 3
push_back 4
push_front 5
pop_back
pop_front

Contoh Keluaran

3
1
2

---

So, the answer is :