CMG  Collecting Mango
One day after storm mina went to pick up mangoes in the garden with a basket. She began to pick up mangoes from the garden. And if she wants, she can throw away the last picked up mango from the basket. In this way, mina kept picking up mangoes. She brought you with her to keep track of the biggest size of mango in the basket at that time. At any moment Mina can ask you about the biggest size of mango. Your job is to help Mina.
Since you are a good programmer, so you write a program by which you are easily able to answer the question of Mina.
During picking up mangoes, Mina can have 3 types of question/instruction for you.
1. Type 1: put an ‘x’ size mango in the basket, which is picked up form garden.
2. Type 2: Throw out last picked up mango. (There can be consecutive throw out operation. )
3. Type 3: Ask for the biggest mango size in the basket at that moment.
Input
The first line contains a positive integer T, number of test case. In the following each case start with a positive integer N, which is number of question/operation Mina will ask during picking up mangoes. Next N lines will contain 3 types of operations (A, R, Q). A x, here x is picked up mango size. R, throw out last picked up mango from basket. Q Find out the biggest size mango.
Output
For each case, first print the case number and print the answer of Mina’s question. Whenever the basket is empty, then Mina’s question’s answer will be “Empty”.
Constraints
 1<=T<=25
 1<=N<=100000
 1<=x<=100000
Example
Input:2
6
A 10
A 5
Q
A 100
R
Q
6
A 5
Q
R
Q
R
R Output:Case 1:
10
10
Case 2:
5
Empty
hide comments
aj_254:
20190511 20:01:50
solved in pypy..using 2 deque and standard i/o ..worth try ... 

Nour Alhadi:
20180825 14:07:48
Very unusual for me, O(n) algorithm with scanf() gives TLE, with ios_base AC :\ :\ 

rajcoolaryan:
20180620 06:00:24
stacks rocked but cin cout shocked 

kaushalag29:
20180619 19:58:28
TLE with ios_base but AC with scanf/printf 

vengatesh15:
20170326 19:40:47
easy one with vectors.. 

rezwanarefin:
20170222 17:01:40
How many of you found algorithm for O(1) append, O(1) out and O(1) max?


Shivam Gupta:
20170126 15:50:44
fast i/o not needed, even n*log^2 n passes in .40 

prakash:
20161128 16:58:27
easy one using fast I/O


lt:
20160827 11:28:37
Linear time algorithm giving TLE :(


Dignesh P R:
20160811 17:08:40
Guys, Any hints? My solution runs in less than 0.2s for 100K operations but still getting TLE. 
Added by:  Anick 
Date:  20160424 
Time limit:  0.5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: GOSU 
Resource:  Own problem. Used in NHSPC 2016 Final Round. More about NHSPC: http://www.nhspc.org/ 