#include <cassert>
#include <iostream>

class StackWithMin
{
    int min;
    int size;
    int data[1024];

  public:
    StackWithMin& push ( int val ) {
        if ( size == 0 ) {
            data[size] = val;
            min = val;
        } else if ( val < min) {
            data[size] = 2 * val - min;
            min = val;

            assert (data[size] < min); 
        } else {
            data[size] = val;
        }

        ++size;

        // check size and grow array
        return *this;
    }

    int getMin () {
        return min;
    }

    int pop () {
        --size;

        int val = data[size];

        if ( ( size > 0 ) && ( val < min ) ) {
            int prevMin = min;
            min += min - val;
            return prevMin;
        } else {
            return val;
        }
    }

    bool isEmpty () {
        return size == 0;
    }
};

int main () {
    StackWithMin stack;

    stack.push(10).push(3).push(6).push(12).push(2).push(6).push(9).push(1);

    while ( ! stack.isEmpty() ) {
        int min = stack.getMin();
        int val = stack.pop();
        std::cout << "popped " << val << ", min " << min << "->"
            << stack.getMin() << '\n';
    }
}