Today is Hubert's first slalom race, and he is nervous. It is also his first day on skis, so he has not learned how to turn yet and can only slide along a straight line. The race is not lost, though. If the designer of this course was careless, it may be possible to pass every gate without turning once.
You are given a slalom course with n gates. The course runs from left to right. Each gate is a vertical segment between two poles. Seen from above, Hubert is a disk of diameter d (d≥0) and the center of the disk moves along a straight line. He may start anywhere to the left of the leftmost gate and finish anywhere to the right of the rightmost gate. To complete the course, his whole body must pass between the two poles of every gate. Touching a pole is allowed.
Find the largest diameter d for which such a straight trajectory exists.