Entrance Examination
Time limit1sMemory limit256 MB
Pick the cutoff n between nmin and nmax with a strict score split that maximizes the gap between the lowest passing and highest failing scores.
- Level
Easy2 of 10
- Topics
- Array, Implementation
- Solved
- No attempts yet
Problem
The International Competitive Programming College (ICPC) is known for its research on competitive programming. Every applicant to the college takes an entrance examination.
The college chooses the successful applicants by these rules.
- The score of every successful applicant is higher than the score of every unsuccessful applicant.
- The number of successful applicants is at least and at most . Within that range, pick the that maximizes the gap. The gap is the lowest score among the successful applicants minus the highest score among the unsuccessful applicants.
- When two or more values of give the same gap, pick the greatest one.
For example, let be 2, let be 4, and let the five scores be 100, 90, 82, 70, 65. For equal to 2, 3, 4 the gaps are 8, 12, 5. The gap is largest at equal to 3, so the answer is 3. With the same and and the scores 100, 90, 80, 75, 65, the gaps are 10, 5, 10. Both 2 and 4 reach the maximum, so pick the greater one, 4.
Given the scores of the applicants, write a program that computes the number of successful applicants.
Input
The input consists of several datasets. Each dataset has this format.
m nmin nmax
P1
P2
...
Pm
The first line holds three integers separated by single spaces. is the number of applicants, is the minimum number of successful applicants, and is the maximum number of successful applicants. Each of the next lines holds one score . The scores are given in descending order, and the same score may appear more than once.
The input satisfies , (), and . An satisfying the rules therefore always exists.
A line holding three zeros separated by single spaces marks the end of the input. Do not process that line.
Output
For each dataset, print the number of successful applicants on its own line.