In computer science, Abstract Data Type (ADT) is some sort of data structures whose behavior is declared without definite implementation. For instance, stack is the data structure with the Last-In-First-Out principle while queue holds the First-In-First-Out one. Both of them can be implemented by either array or linked list.
In C++ Standard Template Library, these ADTs are called container adapters, implemented by template undoubtly. For instance, queue<int> is queue<int, deque<int>> and you can use a vector to be the base of a stack like: stack<int, vector<int>>. In fact, any container support .push_back(), .pop_back() methods can be deemed as a stack, so stack<char, string> is also valid.
Yet template is not generic enough sometimes. In more object-oriented languages like Java, a queue can be declared like Queue<T> q = new LinkedList<>(); or Queue<T> q = new ArrayDeque<>();. As you can see, polymorphism illusrates the relation between an ADT and its implemented data structure in a better way.
Just as Coriolis Force is not a real force, priority queue is not a queue actually but an ADT which supposed to push an element, get and pop the minimum (or maximum) element. Though a binary search tree (BST) can do these all operations in \(O(\log N)\), a heap can do the first two ones in \(O(1)\) average. Hence in pratical, priority queues are implemented by heaps mostly.
Since there are problems about polymorphic stack, queue and priority queue on the OJ and it's midterm, let's have a different ADT: double-ended priority queue (DEPQ). What a double-ended queue (deque) is to a queue is what a DEPQ to a priority queue. So a DEPQ is an ADT that supposed to push an element, get and pop the minimum and maximum elements. A BST can do everything a DEPQ should do, whereas there are other data structtures like min-max heap, double-ended heap (DEAP), symmetric min-max heap and so forth.
But don't worry! Your task is so really simple: implement the polymorphic part of two kinds of the DEPQ. For the BST kind, you can use std::multiset directly, while for the min-max heap, it's done for you in "function.h" so that you can use it!
Since this problem is judged partially, you needn't be concerned about the format of input.
In case your're interested, there are at most \(100\) test cases, each of which started by an integer \(q<10^5\) indicating the number of queries. Then the following \(q\) lines are queries to push an element, print the minimum, print the maimum, pop the minimum, pop the maximum, print the size of the DEPQ.
Since this problem is judged partially, you needn't be concerned about the format of output.
In case your're interested, for each test case, the judge code would print out the maximum, the minimum or the size of the DEPQ if asked by the queries.