바움쿠헨

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