Unusual Permutation

Let $m=r-l+1$. The value $k$ must appear inside the interval, and the other $m-1$ interval values must be chosen from $1$ through $k-1$.

There are $\binom{k-1}{m-1}$ choices for these values, $m!$ orders inside the interval, and $(N-m)!$ orders outside it. Thus the answer is

$$\binom{k-1}{m-1}m!(N-m)!.$$

Precomputing factorials and inverse factorials gives total time complexity $O(\sum N)$.

Solution written by GPT5