Description
A Neo-Stack (Neo Armstrong Cyclone Jet Armstrong Stack) supports the following functions. Your goal is to Implement a Neo-Stack.
-
push(x): push an integer x into the Neo-Stack.
-
top(): return the top-most (the most recent element that is pushed) in the Neo-Stack.
-
pop(): remove the top-most element in the Neo-Stack.
-
maxElement(): return the maximum element currently in the Neo-Stack.
-
popMax(): remove the maximum element currently in the Neo-Stack. If there are multiple maximum elements, remove only the top-most maximum element.
-
minElement(): return the minimum element currently in the Neo-Stack.
-
popMin(): remove the minimum element currently in the Neo-Stack. If there are multiple minimum elements, remove only the top-most minimum element.
(↑ Maybe useful PPAP meme on how to implement Neo-Stack. Ignore this meme if you can't get any idea from Mr. PPAP.)
(APOLOGIZE: Sorry I(Problem setter) don't have enough time to draw a nice Neo Armstrong Cyclone Jet Armstrong Stack. QAQ)
You are encouraged to implement Neo-Stack as a class, for example:
class NeoStack { private: /* anything you need */ /* using STL is welcome */ public: NeoStack() {/* ... */} ~NeoStack() {/* ... */} void push(int x) {/* ... */} void pop() {/* ... */} int top() {/* ... */} int maxElement() {/* ... */} void popMax() {/* ... */} int minElement() {/* ... */} void popMin() {/* ... */} };
Given a sequence of functions mentioned above, please output the result when top() or maxElement() or minElement() is called.
Note : If your algorithm is O(lgn) but get TLE, you can use IO optimization
Input
The first line contains an integer T (1 ≦ T ≦ 10), indicating that there will be T test case in total.
The first line of each test case contains a integer n (1 ≦ n ≦ 1000000), indicating that there will be n functions to be called in this test case.
The next n lines will be the functions. The functions are presented in the following format:
-
push x : push integer x into Neo-Stack, 1 ≦ x ≦ 10^6
-
top : print the top-most element in Neo-Stack in a line
-
pop : remove the top-most element in Neo-Stack
-
maxElement : print the maximum element in Neo-Stack in a line
-
popMax : remove the maximum element in Neo-Stack. If there are multiple maximum elements, please remove the top-most one.
-
minElement : print the minimum element in Neo-Stack in a line
-
popMin : remove the minimum element in Neo-Stack. If there are multiple minimum elements, please remove the top-most one.
It is guaranteed that functions EXCEPT push will not be called when the Neo-Stack is empty.
Important Notes (on how to get AC on more test cases )
There are five test cases in this problem.
In terms of test case size :
-
The first test case is small ( n ≦ 100 ). Mr. PPAP said it is possible to AC this test case using brute force.
-
The second to fifth test case are big ( it is guaranteed that T x n ≦ 4000000 ). Mr. PPAP suggested that the complexity of your solution should be O(lg n).
In terms of test case design :
-
In the first test case : Every function will appear in the first test case. Mr. PPAP said that the test case is very small, why not try brute force? (e.g. O(n) for each function)
-
In the 2nd test case : Only push, pop, top, maxElement, will appear in the 2nd test case. However, the test case is big, Mr. PPAP said that complexity of each function should be less or equal to O(lg n).
-
In the 3rd test case : Only push, pop, top, maxElement, popMax will appear in the 3rd test case. However the test case is still big.
-
In the 4th test case : Only push, pop, top, maxElement, popMax, minElement will appear in the 4th test case. The test case is still big.
-
In the 5th test case : It is a big test case with all kinds of function.
Output
For each test case:
-
Please output "Case #i :"(without quotation mark) in the beginning for each test case, occupying a line, where i is the number of the test case. Notice that there is space before #i and no space after the colon(冒號).
-
For top, maxElement, minElement, please output the required element in a line.