MINSTACK - Smallest on the Stack

Every Christmas the good old man can go to every house in the world and leave gifts for the children who have been good throughout the year, but this is only possible because of his magic gift bag. It would be impossible for Santa to carry all the presents in his bag, the volume and weight of them all makes this obviously unfeasible. What actually happens is that your bag is a kind of magical portal to your gift factory at the North Pole. Where the presents are stacked by their elves and Noel always takes the gift from the top of that pile when he accesses his magical bag.

Gifts have a numerical measure of the degree of fun they can provide children, and Santa is always concerned with the least fun gift he will deliver throughout the night because he does not want any child to feel bad about it. you receive. However, this can not be done in advance because throughout the night as the good old man takes gifts from the pile to deliver, others are still being made and placed on the pile. So the most he can know is the value of the least fun present on the stack up to that point.

Your task is, given the sequence of operations done on the stack of gifts, answer Santa's queries about the value of the least entertaining gift on the stack thus far.

Input

The first line of the input contains an integer N (1 ≤ N ≤ 106) corresponding to the number of operations performed on the present stack. The operations can be of three types: "PUSH V" where V (1 ≤ V ≤ 109) is an integer representing the degree of fun of the present being placed on the stack; "POP" which represents that Santa Claus is taking a gift from the cell to deliver and "MIN" representing a Noel query to know the smallest gift value in the stack.

Output

The output consists of a line containing an integer with the smallest present value in the stack for queries of type "MIN" or "EMPTY" for "MIN" and "POP" operations when the stack is empty.

Example

Input:
11
PUSH 5
PUSH 7
PUSH 3
PUSH 8
PUSH 10
MIN
POP
POP
MIN
POP
MIN

Output:
3
3
5

Example

Input:
9
PUSH 100
PUSH 50
MIN
PUSH 45
MIN
POP
MIN
POP
MIN

Output:
50
45
50
100

Added by:Francisco Elio Parente Arcos Filho [UEA]
Date:2018-12-24
Time limit:1s-1.200s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2024-04-11 13:04:04
time limit in Python. I even used fast input
def fastInput(): return sys.stdin.readline().rstrip("\t\n")
:/
[Simes]: and yet there are AC solutions in both Python2.7 and PyPy2.4:
www.spoj.com/ranks/MINSTACK/lang=PYTH%202.7
www.spoj.com/ranks/MINSTACK/lang=PYPY2.4


Last edit: 2024-04-11 22:13:59
2024-02-26 11:11:50
to avoid TLE , ios_base::sync_with_stdio(0); cin.tie(0); this line is very helpful to reduce time complexity , you can use it like this ,
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
// your code
}
2023-09-01 20:12:40
I am stuck on test case 10!!! can anyone help?
2023-04-23 15:40:37
So weird. With the same solution, I got failed by using Python3 and C++ if using cin and cout. Using scanf and printf instead cin and cout in C++ to avoid TLE.
Using only a single stack to solve this problem.
2022-04-16 21:57:40
time limit exceeded. :/
2020-09-12 09:05:50
showing runtime error using set and map .please help



Last edit: 2020-09-12 09:06:06
2020-09-06 19:03:48
Use '\n' instead of endl. C++
2020-09-06 00:04:27
I got an AC but unnecessarily used multimap in case multiple stocks share the same price. This never happens.,..

Last edit: 2020-09-06 00:04:46
2020-08-03 23:34:35 David
Is the answer to the first test case "3 7 8"?. The first MIN has a value of 3. Two subsequent POPs are 3 then 5. The next MIN is a 7, the next POP is a 7, and the final MIN is an 8.

[NG]: The POPs are 10, 8, 3.

Then the second example doesn't work. If POP removes the max, then a MIN query will not return 100.

[NG]: POP doesn't remove the max. #stack

Thanks for your assistance. I misunderstood the problem. AC.

Last edit: 2021-01-29 00:49:36
2020-06-25 07:15:59
Hi, it's also giving me time limit problem in c++, even for o(1) solution. what's a problem wih this problem.even o(1) is not enough for him. then how can i predict the next move? now do i have to guess!!!!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.