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