Комутуючі функції

Дві функції $\mathbf{f}$ та $\mathbf{g}$ (\mathbf{f}, \mathbf{g}: \mathbf{X} \rightarrow \mathbf{X}) називаються комутуючими, якщо і тільки якщо для кожного $\mathbf{x}$ виконується рівність \mathbf{f}(\mathbf{g}(x)) = \mathbf{g}(\mathbf{f}(x)). Наприклад, функції \mathbf{f}(x) = x+1 та \mathbf{g}(x) = x-2 є комутуючими, а функції \mathbf{f}(x) = x+1 та \mathbf{g}(x) = 2x не є комутуючими.

Кожна функція $\mathbf{h}$ (\mathbf{h}: N_n \rightarrow N_n, де N_n = \{1, 2, \ldots, n\} і $n$ — додатне ціле число) може бути представлена у вигляді списку значень — списку, у якому $i$-й елемент дорівнює $\mathbf{h}(i)$. Наприклад, функція \mathbf{h}(x) = \lfloor x/2 \rfloor з N_5 у N_5 має список значень [1, 1, 2, 2, 3].

Списки значень порівнюються лексикографічно: список [a_1, \ldots, a_n] менший за список [b_1, \ldots, b_n], якщо і тільки якщо існує індекс $k$, такий що a_k < b_k, і для всіх l < k виконується a_l = b_l.

Функція $\mathbf{f}$ (\mathbf{f}: X \rightarrow X) називається бієктивною, якщо для кожного $y$ з $X$ існує рівно один $x$ з $X$, такий що \mathbf{f}(x) = y.

Задано бієктивну функцію $\mathbf{f}$ (\mathbf{f}: N_n \rightarrow N_n, де $n$ — додатне ціле число). Знайдіть таку функцію $\mathbf{g}$, що комутує з $\mathbf{f}$ та має лексикографічно найменший можливий список значень.