{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$ $K$ $Q$\n$A_1$ $A_2$ $...$ $A_N$"},{"iden":"sample input 1","content":"5 3 2\n4 3 1 5 2"},{"iden":"sample output 1","content":"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$."},{"iden":"sample input 2","content":"10 1 6\n1 1 2 3 5 8 13 21 34 55"},{"iden":"sample output 2","content":"7"},{"iden":"sample input 3","content":"11 7 5\n24979445 861648772 623690081 433933447 476190629 262703497 211047202 971407775 628894325 731963982 822804784"},{"iden":"sample output 3","content":"451211184"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}