class MinStack {

        /** initialize your data structure here. */
        private Deque<Integer> deque;
        private Deque<Integer> minDeque;
        public MinStack() {
            deque = new ArrayDeque<>();
            minDeque = new ArrayDeque<>();
        }

        public void push(int x) {
            deque.push(x);
            if (minDeque.isEmpty() || minDeque.peek() >= x) {
                minDeque.push(x);
            }
        }

        public void pop() {
            if (!minDeque.isEmpty() && minDeque.peek().equals(deque.peek())) {
                minDeque.pop();
            }
            deque.pop();
        }

        public int top() {
            return deque.peek();
        }

        public int getMin() {
            return minDeque.peek();
        }
    }