10981098 SUSTech Online Judge
Problem 1098 --Max - Min problem

1098: Max - Min problem

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 113  Solved: 21
[Submit][Status][Web Board]

Description

There are T test cases, for each test case, you will be given n (1<=n<=400000) operations for a stack.

Two possible operations:

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  

Input

the first line is T(1<=T<=5).

for each case, the first line is n(1<=n<=400000) , which is the number of operations, then follows n line contains either operation 1 or operation 2.

Output

for each pop operation, print the (MAX - MIN) value in the remains stack, if the stack is empty, print 0;

Sample Input

1
6
push 387
pop
push 278
push 416
push 111
pop

Sample Output

0
138

HINT


0 is because the stack is empty after the first pop;



138 is calculated by 416 - 278 = 138

Source

stack_and_queue 

[Submit][Status]