Ba vận động viên A, B, C thuộc cùng một đội tham gia giải chạy tiếp sức. Đường đua được chia làm ~n~ chặng đánh số từ 1 tới ~n~ dọc theo chiều dài đường đua, chặng thứ ~i~ có độ dài ~a_i~ mét.

Căn cứ vào thực lực của các vận động viên, huấn luyện viên của đội đề ra chiến thuật chạy thỏa mãn ba yêu cầu sau:

• A sẽ chạy những chặng đầu tiên, tiếp theo là B chạy những chặng kế tiếp, kết thúc là C chạy những chặng cuối cùng.
• Mỗi vận động viên phải chạy nguyên một số (có thể bằng 0) chặng liên tiếp.
• Quãng đường chạy của A ngắn hơn hoặc bằng quãng đường chạy của B, quãng đường chạy của B ngắn hơn hoặc bằng quãng đường chạy của C.

Yêu cầu: Dù A là vận động viên yếu nhất và phải chạy quãng đường ngắn nhất nhưng huấn luyện viên cũng muốn A coi cuộc đua là một cơ hội luyện tập. Vì vậy huấn luyện viên muốn nhờ bạn phân chia chặng đường chạy cho ba vận động viên thỏa mãn cả ba yêu cầu trên mà độ dài quãng đường chạy của A là lớn nhất có thể.

Input

• Dòng 1 chứa số nguyên dương ~n~ (~3 \le n \le 10^6~).
• Dòng 2 chứa ~n~ số nguyên dương ~a_1, a_2, ..., a_n~ cách nhau bởi dấu cách (~a_i \le 10^6~ với mọi ~i~).

Output

Ghi ra một số nguyên duy nhất là độ dài quãng đường chạy của A theo phương án tìm được.

Sample Input 1

6
1000 2000 3000 1000 4000 2000

Sample Output 1

3000

Giải thích:

• A chạy 2 chặng đầu: ~1000 + 2000 = 3000~
• B chạy 2 chặng tiếp: ~3000 + 1000 = 4000~
• C chạy 2 chặng cuối: ~4000 + 2000 = 6000~

Sample Input 2

8
100 1 2 3 4 5 6 7

Sample Output 2

0

Giải thích: A và B không chạy chặng nào, C chạy hết cả đường đua.

Sample Input 3

9
4 2 1 4 1 9 3 3 3

Sample Output 3

6

Giải thích:

• A chạy 2 chặng đầu: ~4 + 2 = 6~
• B chạy 3 chặng tiếp: ~1 + 4 + 1 = 6~
• C chạy 4 chặng cuối: ~9 + 3 + 3 + 3 = 18~

Sample Input 4

11
9 3 1 8 7 1 3 1 1 7 2

Sample Output 4

13

Subtasks

• 30% số điểm ứng với các test có ~n \le 100~.
• 40% số điểm ứng với các test có ~n \le 5000~.
• 30% số điểm ứng với các test không có ràng buộc bổ sung.