{"problem":{"name":"Range Minimum Queries","description":{"content":"You are given an integer sequence $A$ of length $N$ and an integer $K$. You will perform the following operation on this sequence $Q$ times: *   Choose a contiguous subsequence of length $K$, then re","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc098_c"},"statements":[{"statement_type":"Markdown","content":"You are given an integer sequence $A$ of length $N$ and an integer $K$. You will perform the following operation on this sequence $Q$ times:\n\n*   Choose a contiguous subsequence of length $K$, then remove the smallest element among the $K$ elements contained in the chosen subsequence (if there are multiple such elements, choose one of them as you like).\n\nLet $X$ and $Y$ be the values of the largest and smallest element removed in the $Q$ operations. You would like $X-Y$ to be as small as possible. Find the smallest possible value of $X-Y$ when the $Q$ operations are performed optimally.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2000$\n*   $1 \\leq K \\leq N$\n*   $1 \\leq Q \\leq N-K+1$\n*   $1 \\leq A_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $K$ $Q$\n$A_1$ $A_2$ $...$ $A_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc098_c","tags":[],"sample_group":[["5 3 2\n4 3 1 5 2","1\n\nIn the first operation, whichever contiguous subsequence of length $3$ we choose, the minimum element in it is $1$. Thus, the first operation removes $A_3=1$ and now we have $A=(4,3,5,2)$. In the second operation, it is optimal to choose $(A_2,A_3,A_4)=(3,5,2)$ as the contiguous subsequence of length $3$ and remove $A_4=2$. In this case, the largest element removed is $2$, and the smallest is $1$, so their difference is $2-1=1$."],["10 1 6\n1 1 2 3 5 8 13 21 34 55","7"],["11 7 5\n24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784","451211184"]],"created_at":"2026-03-03 11:01:14"}}