Local or Global — Solution & Editorial

Back to the Problem

Counts coincide iff no inversion spans distance ≥ 2 — i.e. max(a_1..i) never exceeds a_i+2. One sweep with a running max.

Complexity: O(N)

Watch out: Counting both quantities separately is O(N log N) and unnecessary — the structural criterion is one pass.