Counting Almost Sorted Permutations

MX noticed an interesting pattern. She considered the following problem: if I fill the remaining entries with numbers (ensuring they form a permutation of 1 through n with all numbers distinct) such that the longest increasing subsequence (LIS) has length \(n-1\), how many ways are there to fill the array?

In other words, given a permutation \(p = [p_1, p_2, \dots, p_n]\) of \(\{1, 2, \dots, n\}\), we say it is almost sorted if:

• The permutation is not completely sorted in increasing order (i.e. not \(1,2,\dots,n\)).
• There exists an increasing subsequence of length \(n-1\); equivalently, the longest increasing subsequence has length exactly \(n-1\).

It can be proved that a permutation of \(\{1,2,\dots,n\}\) has a longest increasing subsequence of length \(n-1\) if and only if it has exactly one descent (i.e. exactly one index \(i\) with \(p_i > p_{i+1}\)). Such permutations are known to have the Eulerian number \(A(n,1)\) as their count. A well‐known formula for \(A(n,1)\) is given by:

[ A(n,1) = 2^n - n - 1. ]

Note that for \(n=1\) the problem is trivial and the interesting cases occur for \(n \ge 2\). Piggy was careful not to fill the same number into different positions, so the numbers form a valid permutation.

inputFormat

The input consists of a single integer \(n\) (\(n \ge 2\)).

outputFormat

Output a single integer, the number of permutations of \(\{1, 2, \dots, n\}\) whose longest increasing subsequence has length exactly \(n-1\). Based on the discussion above, the answer is \(2^n - n - 1\).

sample

2

1