def minimumBribes(q):
    # Can only bribe to move forward. We can take a greedy approach where we sort the 
    # queue from the back, and only allow swaps within a specified window
    # if, by the end of the sort within each window, the last element is not in position,
    # it means they made too many bribes 
    n = len(q)
    window = 3
    num_swaps = 0
    while n >= window:
        swapped = False
        for i in range(1, window):
            # compare with adjacent
            #print(q[n - i], q[n - i - 1])
            
            if q[n - i] < q[n - i - 1]:
                q[n - i], q[n - i - 1] = q[n - i - 1], q[n - i]
                swapped = True
                num_swaps += 1

        if not swapped:
            # window is sorted
            if q[n - 1] != n:
                # last element is unsorted -> someone bribed more than the window
                print("Too chaotic")
                return
            n -= 1
            
    print(num_swaps)
    return num_swaps


q = [4,2,1,3,5,6,7,8]
minimumBribes(q)