2084. Ямы

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

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

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

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

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

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

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

7
0 0 2 0 0 0 1

4.16666666

8
0 0 0 0 0 0 2 0

3.5