24693번 - Implemented Incorrectly 다국어

Consider the following problem:

• You are given a permutation $A = \langle a_1, a_2, \ldots, a_n \rangle$ containing each integer from $1$ to $n$ exactly once. Find its only cyclic shift that starts with $1$.

Consider the following algorithm to solve it:

• Input: $A = \langle a_1, a_2, \ldots, a_n \rangle$.
• For each $i = 2, 3, \ldots, n$:
  • if $a_i < a_1$:
    • rotate $A$ to move $a_i$ to the front; that is, set $A \leftarrow \langle a_i, a_{i+1}, \ldots, a_n, a_1, a_2, \ldots, a_{i-1} \rangle$.
• Output: $A = \langle a_1, a_2, \ldots, a_n \rangle$.

You are given a single integer $n$. Find the number of permutations on which the described algorithm solves the problem incorrectly.

The only line contains a single integer $n$ ($1 \le n \le 42$).

Print the number of permutations on which the described algorithm works incorrectly.

In the first example test case, for $n = 3$, the only permutation resulting in an incorrect output is $\langle 3, 2, 1 \rangle$. The algorithm returns $\langle 2, 1, 3 \rangle$, while the correct answer is $\langle 1, 3, 2 \rangle$.