Trại hè QHHOJ được tổ chức với rất nhiều hoạt động và trò chơi kỳ thú. heygnauq đã vượt qua rất nhiều trò chơi thử thách và đến với giai đoạn cuối cùng là phần thưởng. Có ~N~ thẻ bài được xếp lần lượt thành một hàng. Thẻ bài thứ ~i~ có giá trị phần thưởng là ~a_i~. heygnauq buộc phải chọn ~3~ dãy thẻ bài liên tiếp bất kì. heygnauq không biết lựa chọn như thế nào để được thật nhiều phần thưởng. Bạn hãy giúp heygnauq thực hiện việc này.

~\texttt{Input}~

• Dòng đầu tiên chứa một số nguyên ~N~ là số thẻ bài.
• Dòng thứ hai chứa ~N~ số nguyên là giá trị phần thưởng thẻ bài thứ ~i~.

~\texttt{Output}~

• Gồm một số nguyên duy nhất là kết quả của bài toán

~\texttt{Constraint}~

• ~3 \leq n \leq 10^6~.
• ~|a_i| \leq 10^9~.

~\texttt{Subtask}~

• Subtask ~1~ (~10\%~ số điểm): ~n \leq 10~.
• Subtask ~2~ (~20\%~ số điểm): ~n \leq 10^2~.
• Subtask ~3~ (~30\%~ số điểm): ~n \leq 10^3~.
• Subtask ~4~ (~40\%~ số điểm): Không có giới hạn gì thêm.

~\texttt{Sample Input}~

7
-1 3 -3 5 -2 7 -1

~\texttt{Sample Output}~

15