003 - 手持ち花火 (Sparklers)

JOI 君は自分を含めて N 人の友だちと一緒に手持ち花火で遊ぶことにした．今回使う手持ち花火は, 点火してからちょうど T 秒間だけ燃え続ける．

最初，JOI 君たちは東西に一直線に伸びた道の上に, 1 人につき 1 本手持ち花火を持った状態で散らばって立っている．JOI 君たちには, それぞれ, 1 以上 N 以下の番号が 1 つずつ振られている．ただし，i < j ならば, i 番の人は j 番の人よりも西に立っているか, または, i 番の人は j 番の人と同じ場所に立っているとする．i 番の人は最も西に立っている人(1 番の人) から X_i メートル東に進んだところに立っている．JOI 君は K 番の人である．

花火で遊び始めようとしたとき, 着火するためのライターの燃料の残りが少なく, 1 本の花火に着火することしかできないことに気がついた． そこで JOI 君たちは, まず JOI 君の花火にライターで着火し, その後, 花火から花火へと火を移していくことで他の友だちの花火にも着火することにした．

花火は T 秒間しか燃え続けないので, JOI 君たちは協力して火を移していかなければならない．花火から花火に火を移すためには, 以下の条件を満たさなければならない．

• 火を移す方の花火は, 着火後 T 秒以内の状態でなければならない．着火後ちょうど T 秒経過した状態でもよい．
• 火を移される方の花火は, まだ着火されたことがない花火でなければならない．
• 火を移す方の花火を持っている人と, 火を移される方の花火を持っている人は, 同じ地点に立っていなければならない．

花火の火を移すのにかかる時間は無視できるものとする．

初め JOI 君たちは散らばって立っているので, 火を移すためにはうまく移動しないといけない．JOI 君たちは, それぞれ, 好きな速度で東西の好きな向きに走ることができる．しかし, 遊んでいる最中にあまり速く走るのは危険なので, JOI 君たちは 1 秒あたり s メートル以下の速度で走らなければいけないという速度制限を設けることにした．ここで, s は 0 以上の整数である．

全ての花火に火を移すためには, 速度制限を 1 秒あたり何メートルに設定すればよいだろうか．

課題

花火が燃え続ける時間と JOI 君たちの最初の位置が与えられたとき, 全ての花火に火を移すことが出来るような速度制限であって整数であるものの最小値 s を求めるプログラムを作成せよ．

入力

標準入力から以下のデータを読み込め．

• 1 行目には整数 N, K, T が空白を区切りとして書かれている．これは, JOI 君たちの人数が N 人であり, JOI 君が K 番の人であり, 花火は火をつけてからちょうど T 秒間だけ燃え続けることを表す．
• 続く N 行のうちの i 行目（1 ≤ i ≤ N）には, 整数 X_i が書かれている．これは, 最初, 最も西に立っている人から東に X_i メートル進んだところに i 番の人が立っていることを表す．

出力

標準出力に, 全ての花火に火を移すことが出来るような速度制限であって整数であるものの最小値 s を 1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 1 ≤ K ≤ N ≤ 100 000．
• 1 ≤ T ≤ 1 000 000 000．
• 0 ≤ X_i ≤ 1 000 000 000 (1 ≤ i ≤ N)．
• X₁ = 0．
• X_i ≤ X_j (1 ≤ i ≤ j ≤ N)．

小課題

この課題では小課題は全部で 3 個ある．各小課題の配点および追加の制限は以下の通りである．

小課題1 [30 点]

• N ≤ 20．

小課題2 [20 点]

• N ≤ 1 000．

小課題3 [50 点]

追加の制限はない．

入出力例

入力例 1

3 2 50
0
200
300

出力例 1

2

この入力例では, 速度制限を秒速 2 メートルにすればよい．

まず，1 番の人が東向きに, 2 番の人が西向きに, 3 番の人が西向きにそれぞれ秒速 2 メートルで進む．50 秒後には 2 番の人から 1 番の人に火を移すことができる．

次に，1 番の人が東向きに, 3 番の人が西向きにそれぞれ秒速 2 メートルで進む．25 秒後には 1 番の人から 3 番の人に火を移すことができる．

速度制限を秒速 1 メートルにすると, 全ての花火に火を移すことが出来ない．

入力例 2

3 2 10
0
200
300

出力例 2

8

この入力例では，速度制限を秒速 8 メートルにすればよい．

まず，1 番の人が東向きに, 2 番の人が東向きに, 3 番の人が西向きにそれぞれ秒速8 メートルで進む．

2 番の人は 3 秒後にその場に止まる．1 番の人と3 番の人はそのまま動き続ける．

さらに 6.5 秒後に 2 番の人と 3 番の人が同じ位置に来るが, 火は移さない．2, 3 番の人はその場に止まる．1 番の人はそのまま動き続ける．

さらに 0.5 秒後に 2 番の人から 3 番の人に火を移す．1 番の人はそのまま動き続ける．3 番の人が西向きに秒速 8 メートルで進む．

さらに 9 秒後に 1 番の人と 3 番の人が同じ位置に来る．3 番の人から 1 番の人に火を移す．

速度制限を秒速 7 メートルにすると, 全ての花火に火を移すことが出来ない．

入力例 3

20 6 1
0
2
13
27
35
46
63
74
80
88
100
101
109
110
119
138
139
154
172
192

出力例 3

6