# Approach
# Start with a queue that has zero bribes - with everyone in order
# Move towards the current state of the bribed queue as you count the number of bribes done by someone
# If they exceed three, stop and print 'Too chaotic'
# Otherwise continue with bribing until you reach the final state of the bribed queue
numBribes = {}
positions = {}

rideQueue = None

def bribe(briberPos):
    global rideQueue
    
    bribeePos = briberPos - 1
    # Set the position of the briber to the one infront of him
    briber = rideQueue[briberPos]
    bribee = rideQueue[briberPos - 1]
    positions[briber] = briberPos - 1
    # Set the position of the bribed to the briber's position
    positions[bribee] = briberPos
    
    # Update number of bribes
    numBribes[briber] = numBribes.get(briber, 0) + 1

    # Switch places, bribe the person infront of the briber
    rideQueue[briberPos], rideQueue[bribeePos] = bribee, briber
    
    #print(rideQueue)
    
def isFinalPosBribed(finalPos, currPos):
    # currPos is the position currently held in the queue as the bribes take place
    return currPos > finalPos
    
    
def hasBriberExceededMaxBribes(briberId):
    return numBribes.get(briberId, 0) > 2

def minimumBribes(q):
    global rideQueue
    global numBribes
    global positions
    
    numBribes = {}
    positions = {}
    rideQueue = sorted(q)
    
    i = 0
    while i < len(q):
        finalPos = i
        briberId = q[i]
        unbribedPos = q[i] - 1
        # Get the current position of the person. Remember as the bribes take place, positions change, person 6 may endup infront of 4
        # Implying a person 4 can bribe 6 for as long as they are infront of them
        currPos = positions.get(q[i]) or unbribedPos
        if isFinalPosBribed(finalPos, currPos):
            #print(f"Person: {briberId} bribed")
            while currPos > finalPos:
                # Progress the person towards their bribed position
                bribe(currPos)
                currPos -= 1
                if hasBriberExceededMaxBribes(briberId):
                    print("Too chaotic")
                    return
        else:
            ...
            #print(f"Person: {briberId} didn't bribe")
        i+=1
    #print(rideQueue)
    print(sum(numBribes.values()))