특이한 수열

$m=r-l+1$이라 하자. 구간의 최댓값이 $k$이려면 $k$가 구간에 있어야 하고, 나머지 $m-1$개 값은 $1$ 이상 $k-1$ 이하에서 골라야 한다.

값의 집합을 고르는 방법은 $\binom{k-1}{m-1}$가지이다. 구간 안에 배치하는 방법은 $m!$가지이고, 구간 밖에 배치하는 방법은 $(N-m)!$가지이다. 따라서 답은

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

이다. 팩토리얼과 역팩토리얼을 전처리하면 전체 시간 복잡도는 $O(\sum N)$이다.

Solution written by GPT5