Lexicographically Smallest Quack Sort

Given a data structure Quack, it supports the following methods: insert(x): Insert x into the Quack in sorted order. pop(): Randomly pop an element from the head or tail (either the largest or smallest element). size(): Return the current size of the Quack. The goal is to output the elements in the Quack in ascending order. Input Format: n indicates the number of operations. For the next n lines, each line is an operation. The operations can be of three types: insert x, pop, and size. Output Format: Output the elements in the Quack in sorted order. Example: Input: 6 insert 3 insert 1 insert 2 pop insert 4 size Output: 1 2 4 Constraints: The range of n is [1, 1000]. The element x for insertion is in the range [-1000, 1000]. The solution should aim for a time complexity lower than O(n log n). Example Input 6 insert 3 insert 1 insert 2 pop insert 4 size