001 - 入学試験
時間制限 1 秒 / メモリ制限 256 MB / 得点 10 / x 29 /
問題文
国際競技プログラミング大学 (International Competitive Programming College) は,競技プログラミングの研究でよく知られた大学である. この大学の志願者は入学試験を受験しなくてはいけない.
入学試験の合格者は以下のように選ぶ.
- どの合格者の得点も,どの不合格者の得点より高い.
- 合格者数 n は nmin 人以上,nmax 人以下とする. n はこの範囲内でギャップを最大とするものでなくてはいけない. ギャップとは合格者の最低点と不合格者の最高点の差である.
- 同じギャップになる n が複数あるときは,その中で n が最大になるように選ぶ.
Sample Input の最初のふたつの例を見てみよう. 最初の例では,nmin が 2, nmax が 4 で,5 人の受験者の得点が 100, 90, 82, 70, 65 となっている. 合格者を 2, 3, 4 人としたときのギャップは,それぞれ 8, 12, 5 となる. n としてはギャップが最大となる 3 を選ばなくてはいけない.
2 番目の例では,nmin が 2, nmax が 4 で,5 人の受験者の得点が 100, 90, 80, 75, 65 となっている. 合格者を 2, 3, 4 人としたときのギャップは,それぞれ 10, 5, 10 となる. ギャップは合格者 2 人および 4 人のときに最大となるが,n としてはそのうちの最大の 4 を選ばなくてはいけない.
あなたには,この規則に基づいて合格者数を計算するプログラムを作ってほしい.
Input
入力は複数のデータセットからなる.各データセットは以下の形式で与えられる.
m nmin nmax
P1
P2
...
Pm
各データセットの最初の行は空白ひとつで区切られたみっつの整数からなる. m は受験者の人数,nmin は合格者の最小人数,nmax は合格者の最大人数を表す. その後に続く m 行は,整数 Pi を含むが,これらは各受験者の得点を表す. 得点は高い順に並べられている. これらの数は 0 < nmin < nmax < m ≤ 200, 0 ≤ Pi ≤ 10000 (1 ≤ i ≤ m), Pnmin > Pnmax+1 を満たす. これにより,条件を満たす n が存在することが保証される.
入力の終わりは,空白で区切られたみっつのゼロからなる行によって示される.
Output
各データセットについて,合格者の人数を1行で出力しなさい.
Sample Input
5 2 4 100 90 82 70 65 5 2 4 100 90 80 75 65 3 1 2 5000 4000 3000 4 2 3 10000 10000 8000 8000 4 2 3 10000 10000 10000 8000 5 2 3 100 80 68 60 45 0 0 0
Output for the Sample Input
3 4 2 2 3 2