問題文

長さ 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) の値として考えられる最小の整数を求めてください。

制約

• 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
• 入力はすべて整数である。

入力例 1

5 3 1
1 4 2 8 5

出力例 1

1

入力例 2

6 3 1
30 50 80 85 95 120

出力例 2

3