409977: GYM103886 D Dance Permutations

The Global Cereal Festival (GCF) is happening at CerealLand!

GCF will have $$$n$$$ ($$$1 \leq n \leq 18$$$) attendees, labeled $$$1 \dots n$$$.

In order to engage the crowd, one of the organizers of GCF, Jesse, decides to get them to perform the permutation dance.

In this dance, the attendees stand from left to right, and then permute themselves in every possible manner, from the smallest lexicographic position to the largest lexicographic position.

A permutation $$$a$$$ of length $$$n$$$ is lexicographically smaller than a string $$$b$$$ of length $$$n$$$ if and only if the following holds:

• In the first position where $$$a$$$ and $$$b$$$ differ, $$$a$$$ has a number that is less than the corresponding letter in $$$b$$$.

For example, if $$$n = 3$$$, the attendees would permute themselves in this order:

$$$[1, 2, 3] \rightarrow [1, 3, 2] \rightarrow [2, 1, 3] \rightarrow [2, 3, 1] \rightarrow [3, 1, 2] \rightarrow[3, 2, 1]$$$.

Jesse is interested in knowing the sum of the distances attendee $$$1$$$ moves between successive permutations.

For example, when $$$n = 3$$$, the first attendee moves from position $$$1$$$ in the $$$1$$$st permutation to position $$$2$$$ in the $$$3r$$$d permutation, to position $$$3$$$ in the $$$4$$$th permutation, to position $$$2$$$ in the $$$5$$$th permutation, to position $$$3$$$ in the $$$6$$$th permutation. In total, he moves a distance of $$$1 + 1 + 1 + 1 = 4$$$.

A single integer $$$n$$$.

Output how many times the first members moves in a permutation dance of length $$$n$$$,

3

4

The sample case output is explained in the statement above.

it is important how far attendee $$$1$$$ moves, so $$$[1, 3, 2] \rightarrow [3, 2, 1]$$$ means a distance of $$$2$$$.

Problem Credits: Mythreya Dharani, Ariel Shehter.