Rice Hub#2254
In the countryside, there is a long straight road known as the Rice Way. Along this road, there are rice fields. Each field is located at an integer coordinate between and , inclusive. The rice fields are given in non-decreasing order of their coordinates. Formally, for 0 \leq i < R, the coordinate of field is x_i. It is guaranteed that 1 \leq x_0 \leq x_1 \leq \dots \leq x_{R-1} \leq L.
Note that several rice fields may share the same coordinate.
It is planned to build a single rice hub, where as much rice as possible should be delivered. As with the fields, the rice hub must have an integer coordinate between and , inclusive. The rice hub may be built at any integer coordinate, including where one or more rice fields are already located.
Each rice field produces exactly one truckload of rice per season. To deliver the rice to the hub, a truck driver must be hired, who charges Baht per unit of distance for delivery. That is, the cost of transporting rice from a given field to the hub is equal to the absolute value of the difference of their coordinates.
Unfortunately, the budget for the season is limited: you may spend at most Baht on transportation. It is necessary to place the rice hub so that as many truckloads of rice as possible can be delivered to it without exceeding the budget.
The first line contains three integers , and (1 \leq R \leq 10^5, 1 \leq L \leq 10^9, 0 \leq B \leq 2 \cdot 10^{15}): the number of fields, the maximum coordinate, and the budget, respectively.
The next lines contain integers x_i — the coordinates of the fields (0 \leq i < R). All numbers are sorted in non-decreasing order.
Print the maximum number of truckloads of rice that can be delivered to the hub without exceeding the given budget.
Example 1