Given an integer \$ n \ge 1 \$, your task is to output an array \$ a \$ consisting of \$ n^2 + 1 \$ integers, such that all possible pairs of integers \$ (x, y) \$ satisfying \$ 1 \le x, y \le n \$ exist as a contiguous subarray in \$ a \$, exactly once.
For example, if \$ n = 2 \$, a valid output would be \$ (1, 1, 2, 2, 1) \$. We can check all possible pairs to verify that this is indeed correct:
$$ \begin{align} (1, 1) \to (\color{red}{1, 1}, 2, 2, 1) \\ (1, 2) \to (1, \color{red}{1, 2}, 2, 1) \\ (2, 1) \to (1, 1, 2, \color{red}{2, 1}) \\ (2, 2) \to (1, 1, \color{red}{2, 2}, 1) \\ \end{align} $$
Notes
- It can be shown that a construction exists for all \$ n \$.
- \$ a \$ may be outputted in any reasonable form (e.g. a delimiter-separated string).
- It is recommended, but not required, to prove that your construction works for all \$ n \$.
- This problem is closely related to asking for the de Bruijn sequence of order \$ n \$.
- This is code-golf, so the shortest code in bytes wins.