A ticket office has c identical service counters, numbered 1..c, all free at time 0. n customers arrive at given times (given in non-decreasing order, since they form a single physical line), each requiring a fixed service duration s.
Customers are dispatched strictly in ARRIVAL order (the earliest-arriving customer is assigned a counter first). When a customer needs to be assigned, they go to whichever counter becomes free EARLIEST; ties are broken by the SMALLEST counter number. If that counter's free time is <= the customer's arrival time, the customer starts immediately at their arrival time; otherwise they wait until the counter frees up. After being served, the counter becomes free again exactly s time units after the customer's start time.
Determine the counter number that ends up serving the MOST customers overall. If several counters tie for the most, print the SMALLEST such counter number.
Input format
Line 1: three integers n, c, s.
Line 2: n space-separated non-decreasing integers, the arrival times.
Output format
A single integer: the busiest counter's number (smallest on ties).
Constraints
- 1 <= n <= 100000
- 1 <= c <= 100000
- 1 <= s <= 1000000
- 0 <= arrival time <= 10000000, non-decreasing