11651165 SUSTech Online Judge
Problem 1165 -- Greatest Diﬀerence

## 1165: Greatest Diﬀerence

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

## Description

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.

## Input

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

For each case, the ﬁrst 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.

## Output

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

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


## Sample Output

0
138

## HINT

Hint: 0 is because the stack is empty after the ﬁrst pop.

138 is calculated by 416 - 278 = 138.

[Submit][Status]