ELMO SL 2019 C5

Given a permutation of $1,2,3,\dots,n$ , with consecutive elements $a,b,c$ (in that order), we may perform either of the moves:

• If $a$ is the median of $a$ , $b$ , and $c$ , we may replace $a,b,c$ with $b,c,a$ (in that order)
• If $c$ is the median of $a$ , $b$ , and $c$ , we may replace $a,b,c$ with $c,a,b$ (in that order)

What is the least number of sets in a partition of all $n!$ permutations, such that any two permutations in the same set are obtainable from each other by a sequence of moves?

Proposed by Milan Haiman