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 = *(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