Yami#2361
Winnie-the-Pooh is thrilled—he's just bought a car! To test his new purchase, he plans to drive to a tree where honey awaits.
The road from Winnie-the-Pooh's house to the tree is kilometers long. There are no speed limits in his area, so it might seem he can drive as fast as he wants. However, there's a complication that brings him to you for help.
On some sections of the road, there are potholes. If Winnie-the-Pooh wants to keep his new car safe (which he certainly does), he must drive over each kilometer with potholes at a speed no greater than kilometers per hour. After any kilometer, his car can instantly increase its speed by one, decrease it by one, or leave it unchanged for the next kilometer. After this change, he must travel exactly one kilometer at the new speed, and then he may adjust it again as described.
His car cannot instantly accelerate to any speed, but it can stop immediately (using a brake parachute). Therefore, the first kilometer is always traveled at a speed of kilometer per hour. The speed for the last kilometer is subject only to the restriction of potholes on that kilometer.
Winnie loves driving fast, but loves honey even more. He wants to reach the tree as quickly as possible without damaging his car and asks you to determine the minimum possible travel time.
The first line of the input contains two integers and (1 \leq n,\, k \leq 1000)—the length of the road and the maximum speed allowed on a kilometer with a pothole, respectively. The second line contains numbers, each or , describing the road. A means the kilometer is smooth and can be traversed at any speed, while means there is a pothole and the speed cannot exceed kilometers per hour for that kilometer.
Output one real number: the minimum number of hours Winnie-the-Pooh needs to reach the tree. The answer should not differ from the correct value by more than 10^{-6}.
Example 1