Claim: If a valid arrangement exists, the sorted arrangement works. Proof by exchange: Suppose we have a valid arrangement but the front row is not sorted. There exist positions with . Since the arrangement is valid: and . Swap front[i] and front[j]:
- New pair at i: back[i] vs front[j]. Since , valid.
- New pair at j: back[j] vs front[i]. We need . If , swap works. Otherwise, original arrangement was invalid. By similar argument, sorting back row also maintains validity.