Global Local Solution

Two approaches:

Approach 1: Count both with BIT

• Count global inversions using BIT (as you did before)
• Count local inversions with a simple loop
• Compare

Approach 2: Mathematical insight

• Every local inversion is global
• Extra globals exist iff some $A[i] > A[j]$ for $j > i + 1$
• Check if $|A[i] - i| > 1$ for any $i$ (permutation property)

def isIdealPermutation(A):
    # Approach 2: O(n) without BIT
    for i, val in enumerate(A):
        if abs(val - i) > 1:
            return False
    return True

Sometimes there's a simpler solution than BIT, but the BIT approach teaches the technique.