class MinStack {
 public:
     void push(int x) {
         if(values.empty())
         {
             values.push_back(x);
             min_indices.push_back();
         }
         else
         {
             if( x < values[min_indices.back()] )
                 min_indices.push_back(values.size());
             values.push_back(x);
         }

     }

     void pop() {
         values.pop_back();
         if(values.size() == min_indices.back())
             min_indices.pop_back();
     }

     int top() {
         return values.back();
     }

     int getMin() {
         return values[min_indices.back()];
     }
 private:
     deque<int> values;
     deque<deque<int>::size_type> min_indices;
 };