JOI đang chuẩn bị ăn quà chiều cùng hai em gái JOI-ko và JOI-mi. Món ăn hôm nay là bánh Baumkuchen, món khoái khẩu của cả ba anh em.

Bánh Baumkuchen có dạng hình trụ như Hình 1. Để chia cho ba người, JOI phải cắt bánh thành ba miếng bằng ba nhát cắt theo hướng bán kính. Tuy nhiên, chiếc bánh này cứng như gỗ thật nên không dễ cắt. Vì vậy, trên bánh đã có sẵn \(N\) rãnh cắt và JOI chỉ có thể cắt tại những vị trí này.

Đánh số các rãnh từ \(1\) đến \(N\) theo chiều kim đồng hồ. Với \(1 \le i \le N-1\), phần bánh nằm giữa rãnh thứ \(i\) và rãnh thứ \(i+1\) có độ lớn \(A_i\). Phần bánh nằm giữa rãnh thứ \(N\) và rãnh thứ \(1\) có độ lớn \(A_N\).

Hình 1: Ví dụ về bánh Baumkuchen với \(N = 6\), \(A_1 = 1\), \(A_2 = 5\), \(A_3 = 4\), \(A_4 = 5\), \(A_5 = 2\), \(A_6 = 4\).

Vì thương các em, sau khi cắt bánh thành ba miếng, JOI sẽ chọn miếng nhỏ nhất cho mình và nhường hai miếng còn lại cho hai em gái. Mặt khác, JOI rất thích bánh Baumkuchen nên muốn được ăn càng nhiều càng tốt. Nếu cắt sao cho miếng nhỏ nhất có độ lớn lớn nhất có thể, miếng bánh JOI ăn sẽ có độ lớn bao nhiêu?

Yêu cầu

Cho số rãnh cắt \(N\) và các số nguyên \(A_1, \ldots, A_N\) biểu diễn độ lớn của từng phần bánh. Hãy tính giá trị lớn nhất có thể của độ lớn miếng nhỏ nhất khi chia bánh thành ba miếng.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa số nguyên \(N\), cho biết trên bánh có \(N\) rãnh cắt.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo chứa số nguyên \(A_i\), với \(1 \le i \le N\). Đây là độ lớn phần bánh giữa rãnh thứ \(i\) và rãnh thứ \(i+1\); khi \(i=N\), đó là phần giữa rãnh thứ \(N\) và rãnh thứ \(1\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: giá trị lớn nhất có thể của độ lớn miếng nhỏ nhất khi chia bánh thành ba miếng.

Ràng buộc

• \(3 \le N \le 100\,000\).
• \(1 \le A_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N \le 100\).
• Nhóm 2 (15 điểm): \(N \le 400\).
• Nhóm 3 (30 điểm): \(N \le 8\,000\).
• Nhóm 4 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

6
1
5
4
5
2
4

6

30
1
34
44
13
30
1
9
3
7
7
20
12
2
44
6
9
44
31
17
20
33
18
48
23
19
31
24
50
43
15

213