원형 불꽃놀이

폴리매스 문명 사람들은 불의 돌을 이용해 불꽃놀이를 한 것으로 알려져 있습니다. 불꽃놀이는 원형으로 놓인 $N$개의 폭죽 더미를 사용한 것으로 추정됩니다.

불꽃놀이는 아래 작업을 정확히 $N-2$번 반복하며 진행되었습니다.

• 폭죽 더미를 하나 고릅니다.
• 고른 더미의 폭죽을 모두 터뜨립니다.
• 터진 더미는 사라지고, 양옆으로 가장 가까운 더미의 높이가 각각 1씩 줄어듭니다.

불꽃놀이가 끝나면 두 개의 폭죽 더미만 남습니다. 한 번 사용한 더미는 다시 쓸 수 없습니다. 사람들은 남은 두 더미 높이 중 큰 값을 최소로 만들고자 했습니다. 이 값을 구하는 프로그램을 작성해 봅시다.

첫 줄에 폭죽 더미의 개수 $N$이 주어집니다.

다음 줄에는 각 폭죽 더미의 높이 $A_1, A_2, \cdots, A_N$이 시계 방향 순서대로 주어집니다.

마지막에 남는 두 더미 중 더 높은 더미의 높이의 최솟값을 출력합니다.

• $3 \le N \le 2 \times 10^5$
• $N \le A_i \le 10^9$