Cave Lamp

In a cave near Mirko's village, traces of an ancient settlement remain. Mirko wants to explore it, but he realizes that the cave has no electricity. Because he can afford only one lamp, he wants to place it so that the entire cave floor is visible.

Find the minimum possible y-coordinate of the lamp.

The cave floor is represented as a polyline in the coordinate plane. It consists of N vertices t1, t2, ..., tN and the segments connecting consecutive vertices. The floor always goes from left to right: for every i = 1, ..., N-1, the x-coordinate of ti is smaller than the x-coordinate of ti+1.

The lamp must be placed at a point above the floor. More precisely, its x-coordinate must lie between the x-coordinates of the first and last vertices, inclusive, and its y-coordinate must be at least the floor's y-coordinate at the same x-coordinate.

The lamp illuminates the entire floor if, for every point on the floor, the segment connecting that point to the lamp does not pass through the floor. The segment is allowed to touch the floor at points or overlap with parts of floor segments.

Write a program that determines the smallest y-coordinate at which the lamp can be placed so that it illuminates the entire floor. You may assume that the answer is always at most 1,000,000.

The first line contains an integer N, the number of floor vertices. 2 <= N <= 5000.

Each of the next N lines contains two integers Xi and Yi, the coordinates of the i-th vertex. 0 <= Xi, Yi <= 100000, and the Xi values are strictly increasing in input order.

Output one real number: the minimum y-coordinate at which the lamp can be placed.

An absolute or relative error of at most 0.01 is accepted.