От Андрея убежала его любимая Кракозябра, и он полон решимости ее поймать!

В данный момент беглянка находится в ледяной пещере, в которой с потолка свисают n сосулек, расположенных в точках с целочисленными координатами, пронумерованными от 1 до n. Расстояние от пола до i-й сосульки равняется a_i.

Андрей может выбрать некоторую целочисленную точку T в пределах от 1 до n включительно и в момент времени 0 пустить в обе стороны от нее звуковую волну, распространяющуюся со скоростью одна единица в секунду. Сосулька, которую задело звуковой волной, начинает падать с аналогичной скоростью (то есть за одну секунду расстояние от пола от сосульки уменьшается на один, но не может стать меньше нуля). Пока расстояние от пола до сосульки больше нуля, под ней можно свободно перемещаться; как только сосулька касается пола, она перекрывает проход и делает перемещение невозможным.

Кракозябра изначально (т.е в момент времени 0) находится в точке с координатой и бежит вправо со скоростью одна единица в секунду. Можно считать, что в любую секунду сначала происходит перемещение Кракозябры, а уже затем распространение звука и падение сосулек; в частности, это означает, что если Кракозябра находится в точке , а падающая сосулька в точке i находится на высоте 1 от пола, то кракозябра успеет под ней пробежать и окажется в точке , после чего сосулька окончательно упадет и заблокирует проход.

Кракозябра считается пойманной в тот самый момент, когда и слева, и справа от нее находится хотя бы по одной упавшей (то есть с a_i = 0) сосульке. Помогите Андрею найти минимально возможное время, за которое этого можно добиться путем выбора оптимального значения T, или скажите, что Кракозябра избежит поставленной им ловушки.