A room has n seats with distinct positive integer numbers. The numbers may have gaps. Initially, every seat is available.
Process the following commands in the order given:
BOOK x: reserve the available seat with the smallest number greater than or equal tox, and print its number. If there is no such seat, print-1and leave the reservations unchanged.FREE x: make seatxavailable again. This command prints nothing. The input guarantees thatxis a currently reserved seat.
Input
The first line contains two integers n and q. The second line contains the n seat numbers in arbitrary order. The next q lines each contain one command.
1 <= n, q <= 200000- Every seat number and command argument is between
1and1000000000. - A
BOOKargument need not be a seat number.
Output
For each BOOK command, print the reserved seat number or -1 on its own line. Do not print anything for FREE commands.
Sample input
3 5
10 20 40
BOOK 15
BOOK 15
FREE 20
BOOK 15
BOOK 41
Sample output
20
40
20
-1
Library note
For an ascending std::set, the member function lower_bound(x) returns an iterator to the first element greater than or equal to x, or end() if no such element exists. Insertion, this member function, and erasure by key each take O(log m) time when the set contains m elements. You can also erase by iterator; averaged over a sequence of operations, this takes constant time per erasure.
You may use these operations without implementing a tree or proving their complexity. Any correct solution that meets the resource limits is accepted.
