is doing a contest. He comes across the following problem:
You have an array of elements. There are operations you need to perform on it.
Each operation is one of the following:
I vInsert into the array.
R vRemove a single element from the array with a value of , if it exists.
S vOutput the smallest element in the array. It is guaranteed that does not exceed the size of the array.
L vOutput the index, starting from , of the first occurrence of in the array, if the array was sorted. Output if is not present in the array.
After all of the operations, print out all of the elements remaining in the array in non-decreasing order.
To enforce performing operations in an online manner, will be encrypted.
At any time, every element in the array is between and , inclusive.
per operation. He practices different data structures every day, but still somehow manages to get them wrong. Will you show him a working example?knows that one fast solution uses a Binary Search Tree. However, he knows that a standard binary search tree has a worst case runtime of
Not a binary search tree.
The first line has and .
The second line has integers, the original array.
The next lines each contain an operation in the format
C x, where is the type of operation. is encrypted: you should decode it by finding , where is the answer to the previous
L operation (or if neither operation has occurred). You should perform the operation using . denotes the bitwise XOR operation.
L operation, output the answer on its own line.
After all operations have been finished, output all of the elements in the final array in non-decreasing order on a single line.
5 8 9 4 8 11 2 S 4 I 1 S 13 R 10 L 10 L -5 I 8 L 8
Sample Input (Not Encrypted)
For your convenience, here is a version of the sample input that is NOT encrypted. Remember, all of the real test files will be encrypted (like the input above).
5 8 9 4 8 11 2 S 4 I 8 S 4 R 2 L 2 L 4 I 9 L 9
9 8 -1 1 4 4 8 8 9 9 11