Good Bye 2018 D New Year and the Permutation Concatenation

https://codeforces.com/contest/1091/problem/D

The sum is N(N+1)/2 is equivalent to the sequence is a permutation. For N=10, we have two permutations

AAAABBBBBB CCCCDDDDDD

When BBBBBBCCCC is a permutation, BBBBBB is not sorted in descending order. That's why, if BBBBBB is not descending order, since AAAABBBBBB < next(AAAABBBBBB)=CCCCDDDDDD <= AAAA + reverse_sort(BBBBBB), BBBBBBCCCC is a permutation, if it is descending order, since we cannot get larger permutation by rearranging BBBBBB, we should use the number in BBBBB to CCCC in CCCC. Therefore, BBBBBBCCCC cannot be a permutation. So we only have to find the number of permutations satisfying such a property, and this is

\begin{align}
N!+\sum_{k=1}^{N-1} \left(N! - \frac{N!}{k!}\right)
\end{align}