11651165 SUSTech Online Judge
Problem 1165 -- Greatest Difference

1165: Greatest Difference

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 944  Solved: 211
[Submit][Status][Web Board]


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. 


The first line is an integer T(1<=T<=5).

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.

Sample Input

push 387
push 278
push 416
push 111

Sample Output



Hint: 0 is because the stack is empty after the first pop.

138 is calculated by 416 - 278 = 138.