29400번 - Ямы 스페셜 저지다국어

У Винни-Пуха большая радость --- он купил автомобиль. И теперь, чтобы опробовать покупку, он собрался съездить на нем за медом.

От дома Винни-Пуха до дерева с правильными пчелами, дающими правильный мед, ведет дорога длиной $n$ километров. Казалось бы, скорость передвижения на автомобиле там, где живет Винни, не регламентирована, и ехать можно сколь угодно быстро. Однако, если бы все было так просто, Винни бы не стал обращаться к Вам.

В некоторых местах на дороге расположены ямы. И, если Винни-Пух хочет сохранить свое новое авто в целости и сохранности (а он, конечно же, хочет), проезжать километр номер $i$, на котором расположена яма, нужно со скоростью, не превышающей $a_i$ километров в час. Конструкция автомобиля такова, что после каждого проеханного километра он может мгновенно ускориться на один километр в час, замедлиться на эту же скорость или оставить скорость своего движения без изменений. При этом после изменения он будет ровно километр ехать с новой скоростью, после чего снова сможет ее изменить.

Еще одна особенность автомобиля заключается в следующем: он не может мгновенно разогнаться до нужной скорости, зато может мгновенно остановиться (выбросив тормозной парашют). Соответственно, первый километр пути он всегда проедет со скоростью $1$ километр в час, а скорость на последнем километре может быть ограничена только наличием на этом километре ям.

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

В первой строке входного файла дано одно целое число $n$ ($1 \le n \le 10^5$) --- длина дороги. В следующей строке дано $n$ чисел $a_i$ ($0 \le a_i \le 10^5$) --- описание дороги. Если $a_i$ равно $0$, это означает, что соответствующий километр дороги ровный и его можно проезжать с любой скоростью. Иначе километр содержит яму и его можно проехать со скоростью, не превышающей $a_i$ километров в час.

Выведите в выходной файл одно вещественное число --- минимальное количество часов, за которое Винни-Пух доедет до дерева. Ответ должен отличаться от правильного не больше, чем на $10^{-6}$.