QueueMin

    static class QueueMin {
        int[] a;
        int head;
        int tail;

        public QueueMin(int n) {
            a = new int[n];
            head = tail = 0;
        }

        void add(int x) {
            while (tail > head && a[tail - 1] > x) {
                --tail;
            }
            a[tail++] = x;
        }

        int getMin() {
            if (tail - head == 0) {
                return Integer.MAX_VALUE;
            }
            return a[head];
        }

        void poll(int x) {
            if (a[head] == x) {
                ++head;
            }
        }
    }