통금

Instructors of Some Informatics School 학생들을 잠자리에 들게 한다.

기숙사에는 n개의 방이 있으며, 각 방에서는 정확히 b명의 학생이 자게 되어 있었다. 그러나 통금 시간이 되었을 때 많은 학생이 배정된 방에 있지 않았다. 방들은 일렬로 배치되어 있으며 1부터 n까지 번호가 매겨져 있다. 처음에 i-th번 방에는 ai명의 학생이 있다. 모든 학생은 현재 기숙사 안 어딘가에 있으므로, a1 + a2 + ... + an = nb이다. 또한 이 기숙사에는 2명의 사감이 산다.

통금을 단속하는 과정은 다음과 같다. 한 사감은 1번 방 근처에서 시작하여 n번 방을 향해 이동하고, 두 번째 사감은 n번 방 근처에서 시작하여 1번 방을 향해 이동한다. 현재 방의 처리를 마치면 각 사감은 다음 방으로 이동한다. 두 사감은 동시에 방에 들어가고 이동하며, n이 홀수이면 가운데 방은 첫 번째 사감만 처리한다. 모든 방이 처리되면 과정이 끝난다.

사감이 방을 처리할 때는 방에 있는 학생 수를 센 다음 불을 끄고 방을 잠근다. 또한 처리 중인 방 안의 학생 수가 b와 같지 않으면, 사감은 이 방의 번호를 수첩에 적는다(그리고 불을 끄고 방을 잠근다). 사감들은 다음 날의 학습 계획을 준비하느라 서두르고 있으므로, 방에 누가 있는지는 신경 쓰지 않고 학생 수만 신경 쓴다.

사감들이 방 안에 있는 동안 학생들은 잠기지 않았고 처리 중이지도 않은 방들 사이를 달려서 이동할 수 있다. 학생은 최대 d개의 방만큼 이동할 수 있다. 즉, 현재 방과 번호 차이가 최대 d인 방으로 이동할 수 있다. 또한 각 학생은 달린 후에(또는 달리는 대신) 자신이 있는 방의 침대 밑에 숨을 수 있다. 이 경우 사감은 방을 처리할 때 그 학생을 세지 않는다. 각 방에서는 원하는 수의 학생이 동시에 숨을 수 있다.

형식적으로는 다음과 같은 일이 일어난다.

• 통금이 공지되며, 이 시점에 i번 방에는 ai명의 학생이 있다.
• 각 학생은 처음 있던 방에서 d개보다 멀리 떨어지지 않은 다른 방으로 달려가거나 제자리에 머무를 수 있다. 그 후 각 학생은 선택적으로 침대 밑에 숨을 수 있다.
• 사감들은 1번 방과 n번 방에 들어가 그곳의 학생 수를 세고 방을 잠근다(그 후에는 누구도 이 방에 들어가거나 이 방에서 나갈 수 없다).
• 번호가 2부터 n - 1까지인 방에 있는 각 학생은 현재 방에서 d개보다 멀리 떨어지지 않은 다른 방으로 달려가거나 제자리에 머무를 수 있다. 각 학생은 선택적으로 침대 밑에 숨을 수 있다.
• 사감들은 각각 1번 방에서 2번 방으로, n번 방에서 n - 1번 방으로 이동한다.
• 이 과정은 모든 방이 처리될 때까지 계속된다.

첫 번째 사감이 센 숨지 않은 학생의 수가 b와 달랐던 방의 수를 x1라고 하고, 두 번째 사감에 대한 같은 수를 x2라고 하자. 학생들은 교장이 하나의 불만만 들을 것임을 알고 있으므로, xi의 최댓값을 최소화하려 한다. 학생들이 최적의 전략을 사용할 때 이 값을 구하도록 도와주자.

첫 줄에는 세 정수 n, d, b (2 ≤ n ≤ 100 000, 1 ≤ d ≤ n - 1, 1 ≤ b ≤ 10 000)가 주어진다. 이들은 기숙사의 방 수, 학생이 달려갈 수 있는 거리, 방의 공식 학생 수를 나타낸다.

둘째 줄에는 n개의 정수 a1, a2, ..., an (0 ≤ ai ≤ 109)가 주어지며, 그중 i-th는 통금 공지 전에 i-th번 방에 있던 학생 수를 나타낸다.

a1 + a2 + ... + an = nb임이 보장된다.

xi의 최댓값으로 가능한 최솟값을 나타내는 정수 하나를 출력한다.

첫 번째 예제에서는 앞의 세 방을 첫 번째 사감이 처리하고, 뒤의 두 방을 두 번째 사감이 처리한다. 최적 전략 중 하나는 다음과 같다. 먼저 학생 세 명이 5번 방에서 4번 방으로 달려가고, 다음 단계에서 그중 두 명이 3번 방으로 달려가며, 그 두 명 중 한 명은 침대 밑에 숨는다. 이렇게 하면 첫 번째 사감은 2번 방을 적고, 두 번째 사감은 아무것도 적지 않는다.

두 번째 예제에서 최적 전략 중 하나는 다음과 같다. 먼저 1번 방의 모든 학생이 숨고, 2번 방의 모든 학생이 3번 방으로 달려간다. 다음 단계에서 학생 한 명이 3번 방에서 4번 방으로 달려가고, 5명의 학생이 숨는다. 이렇게 하면 첫 번째 사감은 1번 방과 2번 방을 적고, 두 번째 사감은 5번 방과 6번 방을 적는다.