import java.util.Comparator;

public class DTree {

    //  Priority queues implemented as binary decision trees.

    //  This version is not safe for concurrent use.

    //  The queue item (key) is in the range 0 .. size - 1.

    //  The nodes of the decision tree are mapped to integers in the
    //  range 0 size - 1, in the same way as they are for the
    //  Heapsort algorithm.  That is, the root is at data[1], and for each
    //  node N, the left-child of N is at 2*N and the right-child of N
    //  is at 2*N+1.  Thus, the  parent of N is at N/2.
    //  The sibling of N is at 4*(N/2)-N-1, i.e., at 4*P-N+1 where P
    //  is the parent of N.

    //  There is a leaf location L(I) = size + I + 1 for each value I
    //  in 0 .. size-1.

    //  The value stored at a leaf L(I) (i.e., data(L(I)) is either
    //  (a) I if I is in the queue, or
    //  (b) size, if I is not in the queue.

    //  Thus item I is in the queue iff data(L(I))=I.

    //  The value stored at an interior node is the minimum of the values
    //  stored at each of its two children.

    //  Thus the minimum item in the queue is data[1].

    //  The value size must compare as greater than or equal to
    //  every other item, according to the generic parameter
    //  comparision function.

    //  Any node that is a parent of a node assigned to
    //  a value is an interior node (not a leaf).

    //  The full range of position numbers used by the tree is thus:
    //  1..size  : for interior nodes;
    //  size+1..2*size : for leaves

    //  To verify that no interior node is also a leaf, observe
    //  that the parent of 2*max_size is (2*max_size)/2 = max_size.

    private int[] data;
    private int max_size;
    private int offset; 
    private Comparator<Integer> comparator;

    DTree (int max_size,
           Comparator<Integer> comparator) {
        this.max_size = max_size;
        this.comparator = comparator;
        data = new int[2*max_size + 1];
        for (int i = 1; i < data.length; i++) {
            data[i] = max_size;
        }
    }

    public boolean add (int x) {
        int L = x + max_size + 1;
        if (comparator.compare (data[L], x) == 0) return false;
        for (;;) {
            data[L] = x;
            if (L == 1) break;
            L = L / 2 ;
            if (comparator.compare (data[L], x) <= 0) break;
            // i.e. if data[L] <= x
        }
        return true;
    }

    public boolean contains (int x) {
        return data[x + max_size + 1] == x;
    }

    public boolean isEmpty () {
        return data[1] == max_size;
    }

    public int peek () {
        return data[1];
    }

    public boolean remove (int x) {
        int L = x + max_size + 1;
        int m = max_size;
        int n, p;
        for (;;) {
            if (comparator.compare (data[L], x) != 0) return false;
            data[L] = m;
            if (L == 1) return true;
            p = L / 2; // L's parent
            n = data[4 * p - L + 1]; // L's sibling
            if (comparator.compare (n, m) < 0) m = n;
            // i.e. if n < m
            L = p;
        }
    }

    public int poll () {
        int result = data[1];
        remove(result);
        return result;
    }

    public void clear () {
        for (int i = 1; i < 2 * max_size + 1; i++) {
            data[i] = max_size;
        }
    }
  }