D. Отбой
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Преподаватели Летней Какой-нибудь Школы укладывают учащихся спать.

Домик состоит из n комнат, в каждой из которых должны жить ровно b школьников. Однако к моменту отбоя оказалось, что далеко не каждый школьник находится в своей комнате. Комнаты расположены в ряд и пронумерованы по порядку от 1 до n, изначально в i-й комнате находятся 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 переходит преподаватель.
  • Процесс продолжается, пока во всех комнатах школьники не будут уложены спать.

Пусть первый преподаватель записал x1 комнат с видимым нарушением численности (комнат, где число не спрятавшихся школьников не равно b), а второй 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-е из которых соответствует количеству школьников в i-й комнате перед объявлением отбоя.

Гарантируется, что a1 + a2 + ... + an = nb.

Выходные данные

Выведите одно число — минимальное возможное значение максимального xi.

Примеры
Входные данные
5 1 1
1 0 0 0 4
Выходные данные
1
Входные данные
6 1 2
3 8 0 1 0 0
Выходные данные
2
Примечание

В первом примере первые три комнаты посетит первый преподаватель, а последние две — второй. Одним из оптимальных решений является следующее: на первом шаге три школьника должны перебежать из комнаты 5 в комнату 4, на втором шаге два из них должны перебежать в комнату 3 и одному из них следует там спрятаться. Тем самым недовольство первого преподавателя вызовет только комната 2, а второй преподаватель и вовсе не встретит никаких нарушений.

Во втором примере одной из оптимальных стратегий является следующая: на первом шаге все школьники из комнаты 1 прячутся, а все школьники из комнаты 2 перебегают в комнату 3. На втором шаге один школьник перебегает из комнаты 3 в комнату 4, а ещё 5 прячутся. Тем самым первый преподаватель будет недоволен комнатами 1 и 2, а второй — комнатами 5 и 6.