Count minimum bribes in a queue

Problem People in a queue are numbered by initial position. Anyone may bribe the person directly ahead to swap, at most twice total per person. Given the final ordering, compute the total number of bribes, or report "Too chaotic" if any person moved forward more than 2.

Input / Output

• Input: int array q (final positions of initially-sorted people).
• Output: total bribes, or the chaos report.

Constraints

• n up to 10^5; O(n^2) naive counting passes small cases; the expected solution is near-linear.

Example

• [2,1,5,3,4] → 3; [1,2,5,3,4] → 2; [5,1,2,3,7,8,6,4] → Too chaotic (5 moved up 4).

Expected approach

• Validity: q[i] − (i+1) > 2 → chaotic, immediately. Counting: person q[i]'s bribes = how many people with a larger number ended up in front of them; only positions from max(0, q[i]−2) to i−1 can contain such people (anyone further ahead than that would themselves be chaotic) — giving an almost-O(n) bounded inner loop. A BIT/merge-sort inversion count restricted by the ≤2 rule is the general alternative. The bounded-window insight is the crux.