Big AND Circuit

You need a circuit that computes the logical AND of several source signals. The only part you may use is a two-input AND gate, which outputs True if and only if both of its inputs are True.

The circuit must satisfy these conditions.

• Use exactly $N-1$ AND gates, where $N$ is the number of source signals.
• Each source signal connects to exactly one AND gate input.
• Each AND gate input connects to exactly one signal, either a source signal or the output of another AND gate.
• The circuit has no cycles. The output of an AND gate never reaches one of its own inputs.

The circuit output drives an LED. The LED is lit if and only if all source signals are True.

The timing rules are as follows.

• When source signal $i$ changes, the change takes exactly $n_i$ nanoseconds to reach the circuit.
• After an AND gate input changes, the gate output changes exactly $D$ nanoseconds later, if the new inputs actually change the output.
• The LED changes exactly $L$ nanoseconds after its input signal changes.
• Signals travel between gates in 0 nanoseconds.

Build the circuit that minimizes the maximum time from a source change to an LED change, counting only changes that actually flip the LED.

Figure 1: An optimal circuit for each sample input. The numbers on the left are the source signal indices.

The first line contains three integers $N$ ($2 \leq N \leq 4 \cdot 10^5$), $D$, and $L$ ($1 \leq D, L \leq 10^9$). $N$ is the number of source signals, and $D$ and $L$ are as described in the problem.

The second line contains $N$ integers $n_1, n_2, \ldots, n_N$ ($1 \leq n_i \leq 10^9$), where $n_i$ is the number of nanoseconds it takes for a change in source $i$ to reach the circuit.

Print the smallest time $T$ such that some circuit guarantees the LED takes at most $T$ nanoseconds to change whenever a source change would flip it.