Description

Given a mountain as shown in the figure.

You need to place a lamp somewhere on the mountain so that every part of the mountain is visible.

Output the minimum $y$-coordinate. As shown, the + mark indicates the installation point with the minimum $y$-coordinate.

Input Format

The first line contains an integer $N$, indicating that the mountain consists of $N$ points.

The next $N$ lines, from left to right, describe the mountain. Each line contains two numbers $X_i, Y_i$ representing a vertex, and it is guaranteed that $X_i > X_{i-1}$.

Output Format

Output a single line with the minimum $y$-coordinate. Your answer is considered correct if it differs from the standard answer by no more than $0.01$.

6
0 0
10 0
11 1
15 1
16 0
25 0

3.00

Hint

Constraints:

$30 \%$ of the testdata, $1 \le N \le 50$.

$100 \%$ of the testdata, $1 \le N \le 5000$; $0 \le X_i, Y_i \le 100000$, and the answer is guaranteed to be no more than $1000000$.

Translated by ChatGPT 5