from typing import Any


class PriorityQueueUnsorted:
    """A queue of items that can be dequeued in priority order.

    When removing an item from the queue, the highest-priority item is the one
    that is removed.

    >>> pq = PriorityQueueUnsorted()
    >>> pq.is_empty()
    True
    >>> pq.enqueue(1, 'hello')
    >>> pq.is_empty()
    False
    >>> pq.enqueue(5, 'goodbye')
    >>> pq.enqueue(2, 'hi')
    >>> pq.dequeue()
    'goodbye'
    """
    # Private Instance Attributes:
    #   - _items: A list of the items in this priority queue.
    #             Each element is a 2-element tuple where the first element is
    #             the priority and the second is the item.

    _items: list[tuple[int, Any]]  # EXERCISE: try implementing with a dict[int, Any]

    def __init__(self) -> None:
        """Initialize a new and empty priority queue."""
        self._items = []

    def is_empty(self) -> bool:
        """Return whether this priority queue contains no items.
        """
        return self._items == []

    # def enqueue(self, priority: int, item: Any) -> None:
    #     """Add the given item with the given priority to this priority queue.
    #     """
    #     i = 0
    #     while i < len(self._items) and self._items[i][0] < priority:
    #         # Loop invariant: all items in self._items[0:i]
    #         # have a lower priority than <priority>.
    #         i = i + 1
    #
    #     self._items.insert(i, (priority, item))
    #
    # def dequeue(self) -> Any:
    #     """Remove and return the item with the highest priority.
    #
    #     Raise an EmptyPriorityQueueError when the priority queue is empty.
    #     """
    #     if self.is_empty():
    #         raise EmptyPriorityQueueError
    #     else:
    #         return self._items.pop()
    def enqueue(self, priority: int, item: Any) -> None:
        """Add the given item with the given priority to this priority queue.
        """
        self._items.append((priority, item))  # Note the two pairs of parentheses!

    def dequeue(self) -> Any:
        """Remove and return the element of this priority queue with the highest priority.
        Preconditions:
            - not self.is_empty()
        """
        max_index_so_far = 0
        for i in range(1, len(self._items)):
            if self._items[i][0] > self._items[max_index_so_far][0]:
                max_index_so_far = i
        return self._items.pop(max_index_so_far)[1]


class PriorityQueueSorted:
    """A queue of items that can be dequeued in priority order.

    When removing an item from the queue, the highest-priority item is the one
    that is removed.

    >>> pq = PriorityQueueSorted()
    >>> pq.is_empty()
    True
    >>> pq.enqueue(1, 'hello')
    >>> pq.is_empty()
    False
    >>> pq.enqueue(5, 'goodbye')
    >>> pq.enqueue(2, 'hi')
    >>> pq.dequeue()
    'goodbye'
    """
    # Private Instance Attributes:
    #   - _items: A list of the items in this priority queue.
    #             Each element is a 2-element tuple where the first element is
    #             the priority and the second is the item.

    _items: list[tuple[int, Any]]

    def __init__(self) -> None:
        """Initialize a new and empty priority queue."""
        self._items = []

    def is_empty(self) -> bool:
        """Return whether this priority queue contains no items.
        """
        return self._items == []

    def enqueue(self, priority: int, item: Any) -> None:
        """Add the given item with the given priority to this priority queue.
        """
        self._items.append((priority, item))

        # Sort the tuples by priority
        # (This version works if there are no ties in priorities.)
        self._items.sort()

    def dequeue(self) -> Any:
        """Remove and return the element of this priority queue with the highest priority.

        Preconditions:
            - not self.is_empty()
        """
        return self._items.pop()[1]


class EmptyPriorityQueueError(Exception):
    """Exception raised when calling pop on an empty priority queue."""

    def __str__(self) -> str:
        """Return a string representation of this error."""
        return 'You called dequeue on an empty priority queue.'