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 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 có cơ hội tham gia tiếp sức. Vì vậy huấn luyện viên tìm một phương án phân chia các 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ể.

Dữ liệu vào

• Dòng 1: một số nguyên dương ~n \ (3 \leq n \leq 10^6)~
• Dòng 2: ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ cách nhau bởi dấu cách (với ~a_i \leq 10^6~)

Kết quả

Xuất ra một số nguyên duy nhất — độ 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 2 chặng cuối: ~9 + 3 + 3 + 3 = 18~

Bộ test chia làm 3 subtask:

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