### ** minstack**

## 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