class PriorityQueue:
    """Array-based priority queue implementation."""
    def __init__(self):
        """Initially empty priority queue."""
        self.queue = [None]
        self.min_index = 1

    def __len__(self):
        # Number of elements in the queue.
        return len(self.queue)-1

    def append(self, key):
        """Inserts an element in the priority queue."""
        if key is None:
            raise ValueError('Cannot insert None in the queue')
        self.queue.append(key)
        i = len(self.queue)-1
        while (i > 1):
            if (self.queue[i/2] <= self.queue[i]):
                break
            self.queue[i/2], self.queue[i] = self.queue[i], self.queue[i/2]
            i /= 2;

    def min(self):
        """The smallest element in the queue."""
        if len(self.queue) == 0:
            return None
        return self.queue[1]

    def l(self,i): return 2*i
    def r(self,i): return 2*i+1
    def pop(self):
        """Removes the minimum element in the queue.

        Returns:
            The value of the removed element.
        """
        if len(self.queue) == 1:
            return None
        heapsize = len(self.queue)
        oldmin = self.queue[1]
        self.queue[1] = self.queue[len(self.queue)-1]
        i=1
        while(i<heapsize):
            minidx=i
            if(self.l(i)<heapsize and self.queue[self.l(i)] < self.queue[minidx]):
                minidx=self.l(i)
            if(self.r(i)<heapsize and self.queue[self.r(i)] < self.queue[minidx]) :
                minidx=self.r(i)
            if(minidx!=i):
                self.queue[i], self.queue[minidx] = self.queue[minidx], self.queue[i]
                i=minidx
            else:
                break
        self.queue.pop()
        return oldmin