불꽃놀이

시간 제한1초메모리 제한256 MB

요약

안쪽 더미를 N-2번 제거하며, 제거할 때마다 가장 가까운 양쪽 더미의 높이가 1씩 줄어든다. 마지막에 남는 두 더미 중 큰 값의 최솟값을 구한다.

문제

폴리매스 왕국의 사람들은 불의 돌로 불꽃놀이를 한다. 오늘은 $N$ 개의 폭죽 더미를 사용해 불꽃놀이를 하려고 한다.

다음 작업을 정확히 $N-2$ 번 반복해 폭죽을 터뜨린다.

불꽃놀이가 끝나면 폭죽 더미 두 개만 남는다. 한 불꽃놀이에서 사용한 폭죽 더미는 다시 사용할 수 없으므로, 남은 두 폭죽 더미의 높이 중 큰 값을 최소로 만들려고 한다. 이 값을 구하는 프로그램을 작성하시오.

첫 줄에 폭죽 더미의 개수 $N$ 이 주어진다. 다음 줄에 각 폭죽 더미의 높이 $A_1, A_2, \cdots, A_N$ 이 주어진다.

마지막에 남은 두 폭죽 더미 중 더 높은 것의 높이로 가능한 최솟값을 출력한다.