Очередь по росту
Вам дана очередь из n человек, где каждый человек имеет рост, выраженный положительным целым числом. Требуется обработать q запросов, каждый из которых относится к одному из двух типов:
- Напечатать людей с ростом не выше заданного d: удалить и вывести из начала очереди всех людей, чей рост меньше либо равен некоторому значению d, в том порядке, в котором они извлекаются.
- Добавить человека: добавить в конец очереди человека с ростом d.
Необходимо написать программу, которая будет эффективно обрабатывать эти запросы.
Входные данные
В первой строке входных данных содержатся два целых числа n и q, обозначающие количество людей в начальной очереди и количество запросов соответственно (1 ≤ n, q ≤ 100 000).
Вторая строка содержит n целых чисел , где — это рост i-го человека в очереди (1 ≤ ≤ ).
Каждая из следующих q строк описывает один из запросов в одном из форматов:
pop x, если это запрос типа 1, где x — максимально допустимый рост (1 ≤ x ≤ ).
add x, если это запрос типа 2, где x — рост человека, которого нужно добавить в конец очереди (1 ≤ x ≤ ).
Выходные данные
Для каждого запроса типа 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, в указанном порядке. Далее идут шесть запросов:
- pop 5: первые два человека в очереди (рост 5 и 3) имеют рост не выше 5, поэтому их извлекают из начала очереди и выводят в порядке удаления, формируя ответ «5 3».
- add 4: в конец очереди добавляется человек с ростом 4.
- pop 9: первые два человека в очереди (рост 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