#### Registered Users Only

Please login to view and utilize this feature.

## Problem Description

Rar the Cat has developed a new data structure, the *MinStack*!

Rar's data structure supports the following operations:

*push*: pushing an integer*X*to the top of the stack.*pop*: removes the top integer from the stack.*top*: retrieves the value of the top integer on the stack.*getMin*: retrieves the value of the minimum integer in the stack.

There will be a total of *Q* queries to the data structure. Help Rar implement it.

## Implementation Details

This is a function-call question. You are to implement the following functions:

*void push(int X)*: push*X*into the stack.*void pop()*: remove the top element from the stack.*int top()*: returns (but not remove) the top element on the stack.*int getMin()*: returns (but not remove) the minimum element on the stack.

It is guaranteed that *pop*, *top* and *getMin* will not be called when the stack is empty.

You may access the sample grader and solution template from the *Attachments* tab to test your solutions.

## Limits

Subtask 1 (15%): 1 ≤ Q ≤ 10^{3}, 1 ≤ X ≤ 10^{9}.

Subtask 2 (23%): 1 ≤ Q ≤ 10^{5}, 1 ≤ X ≤ 10^{9}.

Subtask 3 (17%): 1 ≤ Q ≤ 3 * 10^{6}, 1 ≤ X ≤ 2.

Subtask 4 (10%): 1 ≤ Q ≤ 3 * 10^{6}, 1 ≤ X ≤ 10^{9}. *pop* will never be called.

Subtask 5 (35%): 1 ≤ Q ≤ 3 * 10^{6}, 1 ≤ X ≤ 10^{9}.

Subtask 6 (0%): Sample Testcases

## Sample Testcase 1

### Input

6 0 5 0 9 2 3 0 1 3

### Output

9 5 1

## Sample Testcase 2

### Input

7 0 3 0 1 3 2 1 0 5 3

### Output

1 1 3

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 15 | 22 | 1.5s | 256MB | Minimum |

2 | 23 | 42 | 1.5s | 256MB | Minimum |

3 | 17 | 20 | 1.5s | 256MB | Minimum |

4 | 10 | 21 | 1.5s | 256MB | Minimum |

5 | 35 | 102 | 1.5s | 256MB | Minimum |

6 | 0 | 2 | 1.5s | 256MB | Minimum |

### Judge Compile Command

g++ grader.cpp ans.cpp -o minstack -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512