Đường đua gồm ~n~ chặng liên tiếp, chặng thứ ~i~ có độ dài ~a_i~. Ba vận động viên ~A,B,C~ lần lượt chạy các chặng đầu, các chặng giữa và các chặng cuối. Mỗi người phải chạy một số chặng liên tiếp, có thể bằng ~0~.

Cần phân chia sao cho quãng đường của ~A~ không lớn hơn quãng đường của ~B~, và quãng đường của ~B~ không lớn hơn quãng đường của ~C~. Hãy tối đa hóa quãng đường của ~A~.

Input

Dòng đầu chứa số nguyên dương ~n~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~.

Output

In ra độ dài lớn nhất có thể của quãng đường do vận động viên ~A~ chạy.

Subtask

• 30% số điểm: ~n \le 100~.
• 40% số điểm: ~n \le 5000~.
• 30% số điểm: ~3 \le n \le 10^6~, ~a_i \le 10^6~.

Ví dụ

6
1000 2000 3000 1000 4000 2000

3000