Editorial-CK1605

The answer is number of inversions if for every elements , there are elements smaller than it on the right.
If we take the advantage of “at most elements” smaller, we can solve it linearly easily. Notice that the max answer can’t be larger than .
Each person will be bribed by the person who is behind him and has smaller number. We can easily simulate this by keeping count of how many times someone has bribed. If someone has bribed more than times, terminate the algorithm. See setter’s code for this approach.

Python code -

t = int(raw_input())
for _ in range(t):
n = int(raw_input())
arr = map(int, raw_input().split())
org = range(n+1)
pos = range(n+1)
cnt = [0]*(n + 1)

ans = 0
invalid = 0
for i in xrange(n - 1, -1, -1):
        if invalid:
            break
        oldp = pos[arr[i]] #Get position in original array
        newp = i + 1
        while oldp != newp:
            ans = ans + 1
            cnt[org[oldp + 1]] += 1
            if cnt[org[oldp + 1]] > 2:
                invalid = 1
                break
            org[oldp], org[oldp+1] = org[oldp+1], org[oldp]
            pos[org[oldp]] = oldp
            pos[org[oldp + 1]] = oldp+1
            oldp = oldp + 1
if invalid:
    ans = "Too chaotic"
print ans
//