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 i<j with front[i]>front[j]. Since the arrangement is valid: back[i]>front[i] and back[j]>front[j]. Swap front[i] and front[j]:
- New pair at i: back[i] vs front[j]. Since back[i]>front[i]>front[j], valid.
- New pair at j: back[j] vs front[i]. We need back[j]>front[i]. If back[j]>front[i], swap works. Otherwise, original arrangement was invalid. By similar argument, sorting back row also maintains validity.