동굴의 등불

미르코의 마을 근처 동굴에는 오래전 사람들이 살았던 흔적이 남아 있다. 미르코는 동굴을 조사하려고 장비를 준비했지만, 동굴 안에는 전기가 없다는 사실을 뒤늦게 깨달았다. 예산이 부족해 등불은 하나만 살 수 있다.

동굴의 바닥 전체를 볼 수 있는 위치에 등불을 두려고 한다. 등불을 가능한 한 낮게 두려면, 등불의 y좌표를 최소 얼마로 해야 하는지 구하라.

동굴의 바닥은 좌표평면 위의 꺾은선으로 나타낸다. 바닥은 N개의 꼭짓점 t1, t2, ..., tN과, 서로 이웃한 꼭짓점을 잇는 선분들로 이루어진다. 바닥은 항상 왼쪽에서 오른쪽으로 진행하므로, 모든 i = 1, ..., N-1에 대해 ti의 x좌표는 ti+1의 x좌표보다 작다.

등불은 바닥 위쪽의 한 점에 놓아야 한다. 정확히는 등불의 x좌표가 첫 번째 꼭짓점과 마지막 꼭짓점의 x좌표 사이에 있어야 하며, 등불의 y좌표는 같은 x좌표에서의 바닥 y좌표 이상이어야 한다.

바닥 위의 모든 점에 대해, 그 점과 등불을 잇는 선분이 바닥을 뚫고 지나가지 않으면 등불이 바닥 전체를 비춘다고 한다. 선분이 바닥과 한 점에서 만나거나, 바닥의 일부 선분과 겹치는 것은 허용된다.

바닥 전체를 비출 수 있도록 등불을 놓을 때 가능한 최소 y좌표를 구하는 프로그램을 작성하라. 답은 항상 1,000,000 이하라고 가정해도 된다.

첫째 줄에 바닥 꼭짓점의 수 N이 주어진다. 2 <= N <= 5000.

다음 N개의 줄에는 i번째 꼭짓점의 좌표 Xi, Yi가 주어진다. 0 <= Xi, Yi <= 100000이며, Xi는 입력 순서대로 엄격히 증가한다.

등불을 놓을 수 있는 최소 y좌표를 한 줄에 출력한다.

정답과의 절대 오차 또는 상대 오차가 0.01 이하이면 정답으로 인정된다.