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

Домик состоит из n комнат, в каждой из которых должны жить ровно b школьников. Однако к моменту отбоя оказалось, что далеко не каждый школьник находится в своей комнате. Комнаты расположены в ряд и пронумерованы по порядку от 1 до n, изначально в i-й комнате находятся a_i школьников. При этом, в домике находятся все проживающие в нём школьники и только они, то есть, a₁ + a₂ + ... + a_n = nb. В домике также живут 2 преподавателя.

Процесс укладывания школьников спать устроен следующим образом. Первый преподаватель встаёт у комнаты 1 и движется в направлении комнаты n, а второй преподаватель — у комнаты n и движется в сторону комнаты 1. Закончив укладывать очередную комнату, преподаватель переходит к следующей, если n нечётно, то среднюю комнату укладывает спать только первый преподаватель. Как только все школьники уложены спать, процесс заканчивается.

Когда преподаватель заходит в комнату, он считает количество школьников внутри, затем тушит свет и закрывает комнату. Дополнительно, если количество школьников внутри не совпадает с b, этот преподаватель записывает номер комнаты в свою записную книжку и всё равно тушит свет и закрывает комнату. Преподаватели очень торопятся составить учебный план на завтра, поэтому игнорируют, кто именно находится в комнате, считая только количество школьников.

Пока преподаватели находятся в комнатах, школьники могут перебегать между ещё не закрытыми и не укладываемыми прямо сейчас комнатами, причём школьник успевает перебежать не более чем на d комнат (то есть, перемещается в комнату с номером, который отличается не более чем на d). Также, после (или вместо) перемещения любой школьник может спрятаться под кровать в той комнате, в которой находится, тогда преподаватель его не заметит при подсчёте. В любой комнате под кроватями могут спрятаться сколько угодно школьников одновременно.

Формально говоря, происходит следующий процесс:

• Объявляется отбой, к этому моменту в комнате i находится a_i школьников.
• Каждый школьник может переместиться в другую комнату, но не далее, чем на d от изначального положения, либо остаться в текущей комнате. После этого желающие спрятаться под кровать прячутся.
• В комнату 1, а также в комнату n заходят преподаватели и укладывают спать всех находящимся там школьников, после чего запирают комнату (после этого нельзя ни войти в комнату, ни выйти из неё).
• Школьники из комнат с номерами от 2 до n - 1 могут переместиться в другие комнаты, убегая не далее, чем на d комнат от своего текущего местоположения, либо остаться в текущей комнате. Желающие спрятаться под кровать прячутся.
• Из комнаты 1 в комнату 2, и из комнаты n в комнату n - 1 переходит преподаватель.
• Процесс продолжается, пока во всех комнатах школьники не будут уложены спать.

Пусть первый преподаватель записал x₁ комнат с видимым нарушением численности (комнат, где число не спрятавшихся школьников не равно b), а второй x₂. Школьники знают, что директор смены будет слушать жалобы на безобразие во время отбоя не более, чем от одного преподавателя домика, поэтому хотят действовать таким образом, чтобы максимальное из чисел x_i было как можно меньше. Помогите им определить, какое минимальное значение эта величина может принимать при оптимальных действиях школьников.