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; the O(n^2) naive count passes small cases, but a near-linear solution is expected.

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).