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~.

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.

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

Input

• Dòng 1 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~).

Output

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