시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 30 21 18 85.714%

문제

폴리매스 왕국의 사람들은 불의 돌을 이용해 불꽃놀이를 합니다. 오늘의 불꽃놀이는 $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$

서브태스크

번호 배점 제한
1 10

$N \le 9$

2 31

$A_1 < A_2 < \cdots < A_N$

3 59

추가 제한 조건이 없습니다.

예제 입력 1

5
7 6 8 6 9

예제 출력 1

6

예제 입력 2

3
7 7 3

예제 출력 2

6

채점 및 기타 정보

  • 예제는 채점하지 않는다.