큰 AND 회로

여러 원천 신호의 논리 AND를 계산하는 회로를 만들어야 합니다. 사용할 수 있는 부품은 입력을 두 개 받는 AND 게이트뿐이며, 두 입력이 모두 True일 때만 True를 출력합니다.

회로는 다음 조건을 만족해야 합니다.

• AND 게이트를 정확히 $N-1$개 사용합니다. 여기서 $N$은 원천 신호의 개수입니다.
• 각 원천 신호는 정확히 하나의 AND 게이트 입력에 연결됩니다.
• 각 AND 게이트 입력은 정확히 하나의 신호에 연결됩니다. 이 신호는 원천 신호이거나 다른 AND 게이트의 출력입니다.
• 회로에 순환이 없습니다. 어떤 AND 게이트의 출력이 자기 자신의 입력으로 다시 들어가지 않습니다.

회로의 출력은 LED에 연결됩니다. 모든 원천 신호가 True일 때만 LED가 켜집니다.

시간 조건은 다음과 같습니다.

• 원천 신호 $i$가 바뀌면, 그 변화가 회로에 도달하는 데 정확히 $n_i$ 나노초가 걸립니다.
• AND 게이트의 입력이 바뀌면, 새 입력 때문에 출력이 실제로 바뀌는 경우에 한해 정확히 $D$ 나노초 뒤에 출력이 바뀝니다.
• LED는 입력 신호가 바뀌고 정확히 $L$ 나노초 뒤에 바뀝니다.
• 게이트 사이의 신호 전달 시간은 0 나노초로 봅니다.

원천 신호가 바뀌어 LED 값이 실제로 바뀌는 경우에, 원천 신호 변화부터 LED 변화까지 걸리는 시간의 최댓값이 가장 작은 회로를 설계하세요.

그림 1: 각 샘플 입력에 대한 최적 회로입니다. 왼쪽 숫자는 원천 신호의 번호입니다.

첫 번째 줄에 세 정수 $N$ ($2 \leq N \leq 4 \cdot 10^5$), $D$, $L$ ($1 \leq D, L \leq 10^9$)이 주어집니다. $N$은 원천 신호의 개수이고, $D$와 $L$은 문제에서 설명한 값입니다.

두 번째 줄에는 $N$개의 정수 $n_1, n_2, \ldots, n_N$ ($1 \leq n_i \leq 10^9$)이 주어집니다. $n_i$는 원천 신호 $i$가 바뀌었을 때 그 변화가 회로에 도달하는 데 걸리는 나노초입니다.

LED가 실제로 바뀌는 원천 신호 변화가 일어날 때, LED가 바뀌기까지 걸리는 시간이 항상 $T$ 나노초 이하가 되도록 하는 최소의 $T$를 출력하세요.