Stack with Min

Lab C++ Advanced 30 points

Implement a stack supporting push X, pop and min in O(1) by keeping a second stack of minimums. Print the minimum for each min command (or empty).

Input

n, then n commands.

Output

One line per min.

Example

Input

8
push 5
push 3
min
push 7
min
pop
pop
min

Output

3
3
5

Sample input available Sample output available

Editor

C++

Hints

Each entry of the min stack is the minimum of everything at or below that level.

Solution explanation

Trading a little extra memory for O(1) queries is a common design move.

Show solution

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    stack<int> values, mins;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int x;
            cin >> x;
            values.push(x);
            mins.push(mins.empty() ? x : min(x, mins.top()));
        } else if (cmd == "pop") {
            if (!values.empty()) {
                values.pop();
                mins.pop();
            }
        } else {
            if (mins.empty()) cout << "empty\n";
            else cout << mins.top() << "\n";
        }
    }
    return 0;
}

Output

Answer