Dải lụa

Cho một dải lụa chiều dài $N$, trên mỗi đơn vị độ dài của dải lụa người ta có ghi một số nguyên $A_i$ (các số được ghi theo thứ tự $A_1,A_2,\dots ,A_N$ từ đầu này đến đầu kia của dải lụa).

Bạn hãy thiết kế một khung hình chữ nhật kích thước $2\times k$ ($k\ge 2$ tùy ý) sau đó trải dải lụa dọc theo khung hình chữ nhật (có thể cắt đi phần thừa hai đầu của dải lụa, dải lụa sau khi cắt phải vừa đủ dài để trải dọc xung quanh khung hình chữ nhật). Khi đó tổng những số nguyên bao quanh khung hình chữ nhật sẽ là điểm của bạn.

Khung $2\times k$ gồm $2k$ ô, mỗi ô ứng với một đơn vị độ dài của dải lụa. Như vậy phần dải lụa giữ lại là một đoạn liên tiếp $A_l,A_{l+1},\dots ,A_r$ có độ dài $r-l+1=2k$ chẵn và không nhỏ hơn $4$, và điểm là tổng các số trên đoạn đó. Bắt buộc phải làm một khung, nên điểm có thể âm.

Yêu cầu: Hãy cho biết bạn có thể đạt tối đa bao nhiêu điểm?

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $N$ ($4\le N\le {10}^6$).
• Dòng thứ hai chứa $N$ số nguyên $A_1,A_2,\dots ,A_N$ ($|A_i|\le {10}^9$ với $1\le i\le N$).

Dữ liệu ra

In ra một số nguyên duy nhất là số điểm lớn nhất mà bạn có thể có được.

Ràng buộc

• $4\le N\le {10}^6$.
• $|A_i|\le {10}^9$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $N\le 300$.
• Subtask 2 ($30\%$ số điểm): $300<N\le 5000$.
• Subtask 3 ($40\%$ số điểm): $5000<N\le {10}^6$.

Ví dụ