Byteasar là một hacker đã giành quyền tham dự IHO, Olympic Tin tặc Quốc tế, năm nay. Một bài thi yêu cầu anh đối đầu với người quản trị hệ thống. Có \(n\) máy tính được đánh số từ \(1\) đến \(n\), nối thành một vòng: máy tính \(i\) nối với máy tính \(i+1\) với mọi \(i=1,\ldots,n-1\), và máy tính \(n\) nối với máy tính \(1\).

Cuộc đấu là một trò chơi giữa Byteasar và người quản trị với các quy tắc sau:

• Byteasar đi trước. Sau đó, người quản trị và Byteasar lần lượt thực hiện các lượt đi xen kẽ.
• Trong lượt đi đầu tiên của mình, Byteasar chọn một máy tính bất kỳ và xâm nhập nó, chẳng hạn bằng cách khai thác lỗ hổng của hệ điều hành.
• Trong lượt đi đầu tiên của mình, người quản trị chọn một máy tính chưa bị xâm nhập và bảo vệ nó, chẳng hạn bằng cách cài các bản cập nhật bảo mật mới nhất.
• Trong mỗi lượt đi tiếp theo, Byteasar có thể không làm gì, hoặc chọn một máy tính chưa bị xâm nhập cũng chưa được bảo vệ, có kết nối trực tiếp với một máy tính đã bị xâm nhập, rồi xâm nhập máy tính được chọn.
• Trong mỗi lượt đi tiếp theo, người quản trị có thể không làm gì, hoặc chọn một máy tính chưa bị xâm nhập cũng chưa được bảo vệ, có kết nối trực tiếp với một máy tính đã được bảo vệ, rồi bảo vệ máy tính được chọn.
• Trò chơi kết thúc ngay khi cả hai người đều không làm gì trong hai lượt đi liên tiếp.

Ban đầu, chưa có máy tính nào bị xâm nhập hoặc được bảo vệ.

Máy tính \(i\) có giá trị \(v_i\), biểu thị giá trị dữ liệu được lưu trên nó. Với mỗi máy tính \(i\) xâm nhập được, Byteasar nhận \(v_i\) điểm. Anh là một hacker khá giỏi nhưng không biết về thuật toán, nên nhờ bạn viết chương trình tính số điểm lớn nhất anh có thể đạt được khi người quản trị chơi tối ưu.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(n\ge2\)), là số máy tính.

Dòng thứ hai chứa \(n\) số nguyên \(v_1,v_2,\ldots,v_n\) (\(1\le v_i\le2000\)), trong đó \(v_i\) là giá trị dữ liệu trên máy tính \(i\).

Dữ liệu ra

In một số nguyên duy nhất là số điểm lớn nhất Byteasar có thể đạt được khi đối đầu với người quản trị chơi tối ưu.

Ràng buộc

• \(2\le n\le500\,000\).
• \(1\le v_i\le2000\) với mọi \(1\le i\le n\).

Phân nhóm

1. 20 điểm: \(n\le300\).
2. 20 điểm: \(n\le5000\).
3. 20 điểm: \(n\le500\,000\) và xâm nhập máy tính \(1\) là một lựa chọn tối ưu cho lượt đi đầu tiên của Byteasar.
4. 40 điểm: \(n\le500\,000\).

Ví dụ

4
7 6 8 4

13

5
1 1 1 1 1

3