NZ-NZMO 2025 Problem 5

Alice plays a game with the Mad Hatter. The Mad Hatter will write two rows of numbers on a blackboard, each a distinct permutation of $\{1,2,\ldots ,n\}$ . On each move, Alice is allowed to swap the positions of the numbers $a$ and $a + 1$ in the first row, for some $1 \leq a < n$ . What is the minimum number of moves Alice needs in order to guarantee that she can turn the first row of numbers into the second, regardless of the permutations the Mad Hatter writes?