Problem E
Pits
Winnie the Pooh is very happy — he bought a car. And now, to test his purchase, he plans to use it to get honey.
The road from Winnie the Pooh’s house to the tree with the right bees that produce the right honey is $n$ kilometers long. It seems that the speed of movement in the area where Winnie lives is not regulated, and he can drive as fast as he wants. However, if everything was that simple, Winnie would not asked you for help.
There are pits (potholes) in some places along the road. If Winnie the Pooh wants to keep his new car intact (and of course he does), he must drive the $i$-th kilometer at a speed not exceeding $a_i$ kilometers per hour. The design of the car allows him to instantly increase the speed by one kilometer per hour, decrease the speed by one kilometer per our, or maintain his current speed after each kilometer traveled. In other words, all speed changes take place instantly between kilometers and each kilometer is travelled at a constant speed.
He travels the first kilometer at a speed of $1$ kilometer per hour, while the speed on the last kilometer can only be limited by the presence of pits on that kilometer since his car will stop instantly at the end.
Winnie loves to drive fast and he loves honey even more. Therefore, he wants to get from his house to the tree as quickly as possible. He asks you to determine how fast he can reach the tree while keeping his car intact.
Input
The first line of the input contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the road. The next line contains $n$ numbers $a_i$ ($0 \le a_i \le 10^5$) — the description of the road. If $a_i$ is equal to $0$, it means that the corresponding kilometer of the road is flat and can be traveled at any speed. Otherwise, the kilometer contains a pit and can be traveled at a speed not exceeding $a_i$ kilometers per hour.
Output
Output a single real number — the minimum number of hours it will take Winnie the Pooh to reach the tree. The answer must differ from the correct one by no more than $10^{-6}$.
| Sample Input 1 | Sample Output 1 |
|---|---|
7 0 0 2 0 0 0 1 |
4.166666667 |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 0 0 0 0 0 0 2 0 |
3.500000000 |