Algorithms and Data Structures

Height Queue

You are given a queue of n people, where each person has a height represented by a positive integer. You need to process q queries, each of which is one of the following two types:
  1. Print Shorter People: Remove and print the heights of all people from the front of the queue whose height is less than or equal to a certain value d in the order they are popped.
  1. Add Person: Add a person to the end of the queue with height d.
Write a program to process these queries efficiently.

Input

The first line of input contains two integers n and q, denoting the number of people in the initial queue and the number of queries, respectively (1 ≤ n, q ≤ 100 000).
The second line contains n integers , where represents the height of the i-th person in the queue (1 ≤ ≤ ).
Each of the next q lines represents a query of the form:
  • pop x if it is a query of type 1, where x is the maximum height allowed (1 ≤ x ≤ ).
  • add x if it is a query of type 2, where x is the height of the person to be added to the end of the queue (1 ≤ x ≤ ).

Output

For each query of type 1, output the heights of the popped people in the order they are popped, separated by spaces, on a separate line.
Input
Output
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

Explanation

The initial queue contains five people with heights 5, 3, 8, 7, and 10, in that order. The six queries are as follows:
  1. pop 5: The first two people in the queue have heights less than or equal to 5, so they are popped from the front of the queue and printed in order, resulting in the output "5 3".
  1. add 4: A person with height 4 is added to the end of the queue.
  1. pop 9: The first two people in the queue have heights less than or equal to 9, so they are popped from the front of the queue and printed in order, resulting in the output "8 7”.
  1. add 9: A person with height 9 is added to the end of the queue.
  1. pop 2: All people in the queue have heights greater than 2, so no one is popped from the front of the queue and printed. The output is an empty line.
  1. pop 11: All people in the queue have heights less than or equal to 11, so they are popped from the front of the queue and printed in order, resulting in the output "10 4 9".
 

Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 10 MB

To check your solution you need to sign in
Sign in to continue