Best problems — $$$\Theta(thinking)$$$, $$$\Theta(thinking+log(writing))$$$, $$$\Theta(thinking+log(knowledge))$$$, $$$\Theta(thinking+log(knowledge)+log(writing))$$$

Good problems — $$$\Theta(thinking+writing+log(knowledge))$$$, $$$\Theta(thinking+reading+log(knowledge))$$$, $$$\Theta(thinking+reading+writing+log(knowledge))$$$

Nice problems — $$$\Theta(thinking+knowledge)$$$, $$$\Theta(thinking+knowledge+writing)$$$,$$$\Theta(thinking+knowledge+writing+reading)$$$

Mediocre problems — $$$\Theta(thinking+reading)$$$, $$$\Theta(knowledge+writing)$$$

Bad problems — $$$\Theta(reading+writing)$$$, $$$\Theta(reading+log(writing))$$$, $$$\Theta(knowledge)$$$

Hell — $$$\Theta(reading)$$$

Calculate number of ways to write all $$$n!$$$ permutations in one line so that every two adjacent elements in line are different.

I am really stuck without any ideas. I even can't calculate for $$$n = 3$$$.

Of course it can be reformulated to smth like: we have $$$k$$$(in particular $$$(n-2)!$$$) pairs $$$(i, j): i\neq j$$$, calculate number of ways to write it in one line so that every two adjacent elements in line are different.

I would be very pleased to find out something faster than $$$O(n*2^{n!})$$$

I got TL12 1352E - Special Elements 81381374, but after changing set to unordered_set 81381997 I got AC, but the first version got TL on test, where the set(and unordered_set) stays empty(because maximum is 1 and P[i + 2] = P[i] + 2 in that test). I thought this was happening because of the organization of set, but version, where i only create set and don't use it at all passed tests 81382268. How can this be explained?