Count inversion without iterating twice

Question

The problem can be found here. This is what I tried but I am getting wrong answer. My logic is this. At any point if the difference between the position in sorted queue and state queue is negative then we add the absolute value of the difference to chaos. Now if I face two consequtive positive difference, and the the number in the previous position is greater then the current one in the state queue, I add 1 to chaos.

def minimumBribes(q):
    truth = None
    old = 0
    chaos = 0
    for i in range(len(q)):
        diff = (i+1)-q[i]
        if diff < -2:
            print("Too chaotic")
            return

        if diff < 0 :
            chaos = chaos + abs(diff)
            truth = True
            continue
        else:
            if truth == True:
                truth = False
                old = q[i]
                continue
            if old > q[i]:
                chaos = chaos + 1


        old = q[i] 
    print(chaos)

Answer 1

It is not possible to count inversions on linear time with comparsions. There is a theoretical bound to it. https://cs.stackexchange.com/questions/74515/can-we-count-the-number-of-inversions-in-time-mathcalon

You can solve it using Fenwick Tree (also known as Binary Indexed Tree). The idea is described here ( https://www.geeksforgeeks.org/count-inversions-array-set-3-using-bit/ ).