Byteasar – một hacker lừng danh với kỹ năng phi thường – đã lọt vào kỳ thi Olympiad Hacking Quốc tế năm nay (IHO). Trong kỳ thi này, một trong những thử thách mà Byteasar phải đối mặt chính là một trò chơi chiến lược căng thẳng với nhà điều hành hệ thống.

Có ~N~ máy tính được đánh số từ ~1~ đến ~N~, mỗi máy tính ~i~ chứa dữ liệu quan trọng có giá trị ~v_i~. Và được nối với nhau thành một mạch vòng. Nghĩa là:

• Máy tính ~i~ được nối trực tiếp với máy tính ~i+1~ ~(i = 1, 2, \dots, N-1)~.
• Máy tính số ~N~ nối trực tiếp với máy tính số ~1~.

Luật chơi:

• Ban đầu, chưa có máy tính nào bị hack hay được bảo vệ.
• Trò chơi diễn ra theo lượt, Byteasar luôn đi trước, sau đó đến lượt nhà điều hành, rồi lại đến Byteasar, và cứ thế luân phiên.
• Trong lượt đầu tiên:
  • Byteasar chọn một máy tính bất kỳ để hack, chiếm được số điểm bằng đúng giá trị dữ liệu trong máy đó.
  • Nhà điều hành chọn một máy tính khác chưa bị hack để bảo vệ. Máy đó bị khóa vĩnh viễn, Byteasar không thể hack.
• Trong các lượt tiếp theo:
  • Byteasar có thể không làm gì, hoặc hack một máy tính chưa bị hack và chưa được bảo vệ, với điều kiện máy tính đó phải nối trực tiếp với một máy tính đã bị hack trước đó.
  • Nhà điều hành có thể không làm gì, hoặc bảo vệ một máy tính chưa bị hack và chưa được bảo vệ, với điều kiện máy tính đó phải nối trực tiếp với một máy tính đã được bảo vệ trước đó.
• Trò chơi kết thúc ngay khi cả hai cùng liên tiếp không thực hiện hành động nào.

Điểm số:

• Mỗi lần Byteasar hack một máy tính ~i~, hắn nhận được ~v_i~ điểm.
• Nhà điều hành thì không ghi điểm, nhiệm vụ của ông chỉ là ngăn Byteasar chiếm được nhiều điểm nhất có thể.
• Byteasar muốn tối đa hóa tổng số điểm, còn nhà điều hành sẽ chơi tối ưu để hạn chế hắn.

Nhiệm vụ: Hãy giúp Byteasar viết chương trình tính số điểm lớn nhất mà hắn có thể đạt được, giả sử cả hai bên đều chơi tối ưu.

Input

• Dòng đầu: số nguyên ~n~ — số máy tính ~(2 \le n \le 500000)~.
• Dòng thứ hai: dãy ~n~ số nguyên ~v_1, v_2, \dots, v_n~ ~(1 \le v_i \le 2000)~

Output

• In ra số điểm lớn nhất Byteasar có thể chiếm được.

Sample Input 1

4
7 6 8 4

Sample Output 1

13

Sample Input 2

5
1 1 1 1 1

Sample Output 2

3

Notes

• Với ví dụ thứ nhất:
  • Byteasar bắt đầu hack máy tính số ~2~, nhận ~6~ điểm.
  • Nhà điều hành ngay lập tức bảo vệ máy tính số ~3~.
  • Byteasar tiếp tục hack máy tính số ~1~, thêm ~7~ điểm.
  • Nhà điều hành bảo vệ máy tính số ~4~.
  • => Tổng cộng Byteasar đạt được ~13~ điểm.