import collections


def _sort_almost_sorted(almost_sorted_deque, key):
    """
    Sort a deque like that where only the first element is potentially unsorted and should probably be last and the rest
     of the deque is sorted in descending order.

    :param collections.deque almost_sorted_deque: The deque of size n, where the first n-1 elements are definitely
        sorted (in descending order) and where the last element is also probably in the correct place, but needs to be
        checked
    :param callable key: The key (function) to use for sorting.
    :return: The sorted (given that the conditions are met) deque.
    :rtype: collections.deque
    """
    if key(almost_sorted_deque[0]) < key(almost_sorted_deque[1]):
        almost_sorted_deque.append(almost_sorted_deque.popleft())
    if key(almost_sorted_deque[-1]) <= key(almost_sorted_deque[-2]):
        return almost_sorted_deque
    almost_sorted_deque = collections.deque(sorted(almost_sorted_deque, key=key, reverse=True))
    return almost_sorted_deque