바움쿠헨
면접 대비시간 제한2초메모리 제한256 MB
원형 케이크를 연속된 세 조각으로 나누어 가장 작은 조각을 최대한 크게 만듭니다.
문제
JOI 군은 동생 두 명과 바움쿠헨을 나눠 먹으려 한다. 바움쿠헨은 원형 케이크이고, N개의 미리 낸 칼금 위치에서만 자를 수 있다. i번 칼금과 i+1번 칼금 사이 조각 크기는 Ai (AN은 N번과 1번 사이)이다.
JOI 군은 케이크를 3조각으로 자른 뒤 가장 작은 조각을 자신이 먹고, 나머지 두 조각을 동생들에게 준다. 이때 가장 작은 조각 크기의 최댓값을 구하라.
입력
- 1행: 정수 N
- 다음 N행: i행에 Ai
출력
3조각으로 나눌 때 가능한 가장 작은 조각 크기의 최댓값을 한 줄에 출력한다.
제한
- 3 ≤ N ≤ 100 000
- 1 ≤ Ai ≤ 1 000 000 000