Global and Local Inversions

Problem Given an array nums of length n that is a permutation of [0, 1, ..., n-1], determine whether the number of global inversions equals the number of local inversions. A global inversion is any pair (i, j) with i < j and nums[i] > nums[j]; a local inversion is a global inversion where j = i + 1.

Input / Output

• Input: array nums — a permutation of 0..n-1
• Output: boolean — true if the global inversion count equals the local inversion count

Constraints

• 1 <= n <= 10^5; nums is guaranteed to be a permutation of [0, n-1] with no duplicates
• Target O(n) time and O(1) space — counting inversions with merge sort at O(n log n) works but misses the point

Example

• nums = [1,0,2] → true — the single inversion (0,1) is both global and local
• nums = [1,2,0] → false — nums[0]=1 > nums[2]=0 is a global inversion but not local
• nums = [0,1,2] → true — zero inversions of either kind