What is the Problem?
Since beginning her university studies, Ava has been going to a nearby plaza for lunch. In order to maintain good eating habits throughout her university career, Ava has crafted a perfect dining strategy.
Ava began by eating at each of the N restaurants (numbered 1 through N) at the plaza and rating how much she enjoyed the food. Once she gathered all the ratings, she would only eat at the highest-rated restaurant. (If there is a tie, she eats at the lowest-numbered restaurant.) However, after a week of eating the same food, Ava realized she needs more variety in her diet. To fix this issue, she decided that eating at a restaurant would cause its rating to drop by a fixed amount, M.
Armed with her dining strategy, Ava wonders where she will grab lunch on her last day of university, which is K days away if she eats at exactly one restaurant per day.
Input Specifications
DATA31.txt (DATA32.txt for the second try) will contain 10 test cases. Each test case starts with three integers N, M, K (1 ≤ N, M ≤ 100,000, 1 ≤ K ≤ 1012). The next line contains N positive integers Rp (1 ≤ Rp ≤ 109), where Rp represents the rating of the pth restaurant at the plaza. Restaurants are numbered starting from 1.
For the first four test cases in the file, N*K ≤ 106. For the first seven cases, K ≤ 106.
Output Specifications
For each test case, your program should output one integer representing the restaurant Ava will eat at on the Kth day.
Sample Input (2 cases shown)
2 5 4
20 17
5 4 7
1 2 4 8 16
4 8 100
3 22 20 14
Sample Output
2
5
3