Một chiếc bánh tròn được chia thành \(N\) miếng đánh số ngược chiều kim đồng hồ. Miếng \(i\) kề miếng \(i-1\) và \(i+1\) (coi miếng \(0\) là \(N\), miếng \(N+1\) là \(1\)), có kích thước \(A_i\); mọi \(A_i\) đôi một khác nhau.

JOI chọn trước một miếng bất kỳ. Sau đó IOI và JOI luân phiên lấy, IOI đi trước. Chỉ được lấy miếng có ít nhất một miếng kề đã bị lấy. Nếu có nhiều lựa chọn, IOI luôn lấy miếng lớn nhất, còn JOI được tùy ý chọn. Hãy tìm tổng kích thước lớn nhất JOI có thể lấy.

Dữ liệu vào

Dòng đầu chứa \(N\). Dòng thứ \(i+1\) chứa \(A_i\).

Dữ liệu ra

In tổng lớn nhất JOI có thể lấy.

Ràng buộc

các \(A_i\) đôi một khác nhau.

Phân nhóm

• Nhóm 1 (15 điểm): \(N\le20\).
• Nhóm 2 (45 điểm): \(N\le300\).
• Nhóm 3 (40 điểm): không có ràng buộc bổ sung.

Ví dụ

5
2
8
1
10
9

18

8
1
10
4
5
6
2
9
3

26

15
182243672
10074562
977552215
122668426
685444213
3784162
463324752
560071245
134465220
21447865
654556327
183481051
20041805
405079805
564327789

3600242976