There are T test cases, for each test case, there are n (1<=n<=400000) operations for a stack. And there are only two operations in this problem.
The following operations are:
1. push x
2. pop
For operation 1 you are asked to push x(1<=x<=100000000) in to the stack.
For operation 2 you are asked to pop out the top element of the stack and print the maximum number of the stack - minimum number in the stack.
For each case, the first line is n(1<=n<=400000) , which is the number of operations, then the following are n lines containing either operation 1 or operation 2.
It is not guaranteed that whether the stack is empty. If the stack is empty and you are asked to pop the element, you can just ignore the operation, but still need to print the corresponding answer.
For each pop operation, print the (MAX - MIN) value in the remaining stack. If the stack is empty, print 0.
For each test case, print each answer in a line.
1
6
push 387
pop
push 278
push 416
push 111
pop
0
138Hint: 0 is because the stack is empty after the first pop.
138 is calculated by 416 - 278 = 138.