City Bike

Time limit2sMemory limit2048 MB

Summary

A truck with capacity c moves bikes among n stations, each holding at most d bikes. Find the smallest possible gap between the fullest and emptiest station.

Level: Medium7 of 10
Topics: Greedy, Binary search, Simulation
Solved: No attempts yet

Problem

City bikes are a popular way to commute. Some docking stations have only a few bikes while others are almost full with few empty docks, which is frustrating for riders. The bike company regularly sends trucks to move bikes between stations to ease this imbalance.

A truck is about to leave the bike center to start a relocation trip. The truck can carry at most $c$ bikes. Before it departs, it may choose an initial load of anywhere from $0$ to $c$ bikes, both inclusive. The truck then visits $n$ docking stations in order. Each docking station can hold at most $d$ bikes, and some bikes are already docked at each station at the start. At each station, the truck may load or unload any number of bikes, as long as the truck does not exceed its capacity $c$ or the station does not exceed its capacity $d$ . The truck does not have to end the trip with the same number of bikes as its initial load. The goal is to minimize the difference between the maximum and minimum number of bikes at any station.

What is the smallest difference that can be achieved?

Input

The first line contains three integers $n$ , $d$ , and $c$ ( $2 \le n \le 2 \cdot 10^5$ , $1 \le d, c \le 10^6$ ), the number of docking stations, the capacity of each docking station, and the capacity of the truck. Each of the next $n$ lines contains a single integer between $0$ and $d$ , both inclusive, the number of bikes that docking station $i$ initially has.

Output

Output a single integer, the smallest achievable difference between the maximum and minimum number of bikes at any docking station.

Examples1

Example 1
Input
```
4 7 3
0
7
2
5
```
Expected output
```
1
```