AT_pakencamp_2025_day1_d Kth abs min

長さ $ N $ の非負整数列 $ A=(A_1,A_2,\dots,A_N) $ と、正整数 $ M,K $ が与えられます。 ここで、整数 $ x $ に対して、 $ f(x) $ を以下のように定義します。 - 長さ $ N $ の非負整数列 $ B $ を $ B_i=|A_i-x| $ で定義する。 $ B $ を値の昇順にソートしたときの $ B_M $ の値を $ f(x) $ とする。 今、あなたは $ A $ の要素を $ 0 $ 個以上 $ K $ 個以下選び、他の非負整数に変更することができます。このとき、 $ f(x) $ の値として考えられる最小の整数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ K $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $

答えを一行に出力せよ。

### Constraints - $ 1 \leq N \leq 5 \times 10^5 $ - $ 1\leq M \leq N $ - $ 0\leq K \leq N $ - $ 0\leq A_i \leq 10^9 $ - 入力はすべて整数である。