해설m=r−l+1m=r-l+1m=r−l+1이라 하자. 구간의 최댓값이 kkk이려면 kkk가 구간에 있어야 하고, 나머지 m−1m-1m−1개 값은 111 이상 k−1k-1k−1 이하에서 골라야 한다. 값의 집합을 고르는 방법은 (k−1m−1)\binom{k-1}{m-1}(m−1k−1)가지이다. 구간 안에 배치하는 방법은 m!m!m!가지이고, 구간 밖에 배치하는 방법은 (N−m)!(N-m)!(가지이다. 따라서 답은 (k−1m−1)m!(N−m)!\binom{k-1}{m-1}m!(N-m)!(m−1k−1)m!(N−m)! 이다. 팩토리얼과 역팩토리얼을 전처리하면 전체 시간 복잡도는 O(∑N)O(\sum N)O(∑N)이다. Solution written by GPT5
