Basically, I though about decomposing the permutation into $k$ subarrays that each subarray satisfies the condition that the next term is +1 the last term. If this is possible, then this permutation is $k$-good We can look at this decomposition as also a permutation. We want the number of permutations that is $n$-good but not $n-1$-good. This makes me want to try out some inclusion-exclusion, similar to counting derangements. The exact expression is done by changing the formula bit-by-bit and compare with brute-force results.