Вася — волшебник, который сражается с монстрами. В очередной раз. В ряд расположены $$$n$$$ монстров, количество очков здоровья $$$i$$$-го монстра равно $$$a_i$$$.

Вася — очень могущественный волшебник и знает очень много мощных заклинаний. В этом сражении он решил использовать цепную молнию, чтобы победить всех монстров. Давайте посмотрим, как работает это заклинание.

Сначала Вася выбирает индекс какого-то монстра $$$i$$$ ($$$1 \le i \le n$$$) и изначальную силу заклинания $$$x$$$. Затем заклинание поражает монстров ровно $$$n$$$ раз, каждого монстра ровно один раз. Первой целью заклинания всегда является монстр $$$i$$$. Каждой целью заклинания, за исключением первой, выбирается случайный монстр, который еще не был поражен заклинанием и является соседним к одному из пораженных монстров. Таким образом, каждый из монстров будет поражен ровно единожды. Первый монстр, пораженный заклинанием, получает $$$x$$$ единиц урона, второй получает $$$(x-1)$$$ единиц урона, третий получает $$$(x-2)$$$ единиц урона, и так далее.

Вася хочет показать, насколько он силен, поэтому он хочет убить всех монстров за одно применение цепной молнии. Монстр считается мертвым тогда, когда его количество очков здоровья меньше либо равно урону, который он получил. С другой стороны, Вася хочет показать, что он не настолько сильно переживает за сражение, поэтому он хочет выбрать минимальную изначальную силу заклинания $$$x$$$, способную убить всех монстров вне зависимости от того, какой монстр (среди тех, кто может получить урон) получит урон на каждом из шагов.

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

Заметьте, что Вася выбирает изначальную цель и силу заклинания, другие события являются случайными и Вася хочет убить всех монстров даже в худшем из возможных исходов.