Height Queue (高さのキュー)
与えられたのは、n 人の人々が並んだキューで、それぞれの人の身長は正の整数で表されます。これに対して q 件のクエリを処理しなければなりません。クエリには2種類あり、いずれかの動作を行います:
- Print Shorter People (高さ d 以下の人を出力): キューの先頭から、身長が d 以下の人々をすべて取り除き、その高さを取り除いた順に出力する。
- Add Person (新しい人を追加): 身長 d の人をキューの末尾に追加する。
このクエリを効率的に処理するプログラムを作成してください。
入力
最初の行には、キューに最初から含まれる人数 n と、処理すべきクエリの数 q の 2 個の整数が与えられます (1 ≤ n, q ≤ 100 000)。
次の行には、n 個の整数 が与えられ、それぞれ はキューの i 番目の人の身長を表します (1 ≤ ≤ )。
続く q 行の各行にはクエリが書かれており、以下のいずれかの形式です:
- 「pop x」: クエリの種類 1 に対応し、x は取り除く人の最大身長 (1 ≤ x ≤ )。
- 「add x」: クエリの種類 2 に対応し、x は末尾に追加する人の身長 (1 ≤ x ≤ )。
出力
クエリの種類が 1（pop）のときには、取り除いた人々の身長を先頭から順にスペース区切りで 1 行に出力してください。
入力 | 出力 |
5 6
5 3 8 7 10
pop 5
add 4
pop 9
add 9
pop 2
pop 11 | 5 3
8 7
10 4 9
|
説明
最初のキューには、順に身長 5、3、8、7、10 の 5 人が並んでいます。これに対して行うクエリは 6 件で、順番は以下のとおりです:
- pop 5: キュー先頭の 2 人(身長 5 と 3)が 5 以下なので取り除かれ、出力に「5 3」が表示されます。
- add 4: 身長 4 の人がキューの末尾に追加されます。
- pop 9: キューの先頭にいる 2 人(身長 8 と 7)が 9 以下なので取り除かれ、「8 7」が出力されます。
- add 9: 身長 9 の人が末尾に追加されます。
- pop 2: キューの先頭にいる人々の身長はすべて 2 より大きいので、誰も取り除かれません。ここでは空行が出力されます。
- pop 11: キューに残っている人々全員(身長 10、4、9)が 11 以下なので、先頭から順に取り除かれて「10 4 9」が出力されます。
Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 10 MB