Mountain Lamp Installation

Given a mountain represented by n points in the plane, with strictly increasing x-coordinates, the mountain is defined by the polyline connecting these points in order. You are required to install a lamp on the mountain (i.e. at one of the given points) so that every point on the mountain is visible from the lamp.

A point P on the mountain is visible from the lamp L if the line segment \(\overline{LP}\) never goes below the mountain. In other words, for every point Q on \(\overline{LP}\), its y-coordinate is not less than the y-coordinate of the mountain at that x-position.

You need to choose a vertex for installation so that the lamp is at a valid position and its y-coordinate is minimized. Output this minimal y coordinate. If no vertex can see the entire mountain, output -1.

The mathematical condition is: Let the mountain vertices be \( (x_1,y_1), (x_2,y_2), \dots, (x_n,y_n) \) with \( x_1 < x_2 < \dots < x_n \). For a chosen vertex \( (x_i,y_i) \) to be feasible, it must satisfy that for every vertex \( (x_j,y_j) \) (with 1 \(\le\) j \(\le\) n), the line joining \( (x_i,y_i) \) and \( (x_j,y_j) \) does not go below the mountain polyline. A simplified way to check this is to precompute two envelopes:

• From the left: For each vertex \( (x_i,y_i) \), define
  \( L(x_i)= y_1 + m_{\text{left}}(x_i - x_1) \) where \( m_{\text{left}} = \max_{1 \le k \le i} \frac{y_k - y_1}{x_k - x_1} \) (with the convention that when \( i=1 \), \( L(x_1)=y_1 \)).
• From the right: For each vertex \( (x_i,y_i) \), define
  \( R(x_i)= y_n + m_{\text{right}}(x_n - x_i) \) where \( m_{\text{right}} = \max_{i \le k \le n} \frac{y_k - y_n}{x_n - x_k} \) (with \( R(x_n)= y_n \)).

A vertex \( (x_i,y_i) \) is a valid candidate if
\( y_i \ge \max(L(x_i),R(x_i)) \). Among all valid vertices, output the minimum y value.

Note: For this problem, you only need to consider installing the lamp at one of the provided vertices.

inputFormat

The first line contains an integer n (n \(\ge\) 3), the number of vertices of the mountain.

The next n lines each contain two integers x and y separated by a space, representing the coordinates of a vertex. It is guaranteed that \( x_1 < x_2 < \dots < x_n \).

outputFormat

Output a single integer, which is the minimal y-coordinate among the valid lamp installation positions. If no vertex can see the entire mountain, output -1.

sample

3
0 0
1 2
2 0

2