Đề bài

Trong các giờ thực hành môn Tin học, các học sinh rất thích sử dụng máy tính để chơi game. Tuy nhiên, trong quy định về môn học thì học sinh lại không được phép. Hôm nay, trong giờ thực hành Tin học về lập trình, thầy giáo đã đưa ra một trò chơi để cho học sinh được giải trí và cũng là để học tập.

Trò chơi có tên là "Bắn đĩa bay". Với trò chơi này, trước khi vào vị trí bắn, người chơi được cho quan sát ~N~ đĩa, trên mỗi đĩa ghi một số nguyên dương tương ứng với điểm có được nếu người chơi bắn trúng.

Súng để bắn đĩa là loại súng thể thao có hai nòng, tại mỗi thời điểm có thể nạp được tối đa ~2~ viên đạn, mỗi lần bóp cò chỉ bắn ra ~1~ viên đạn. Sau khi bắn ~1~ viên đạn hoặc bắn hết ~2~ viên đạn, người chơi có thể nạp lại đạn.

Như vậy, khi hệ thống phóng đĩa hoạt động, người chơi chỉ bắn được tối đa hai đĩa gần nhau rồi phải thực hiện thao tác nạp đạn trước khi muốn bắn tiếp. Biết rằng mỗi lần nạp đầy đạn thì sẽ có một đĩa đã bay qua tầm ngắm và người chơi không thể bắn được đĩa này.

Bạn là một người chơi, giả sử tỉ lệ bắn trúng đĩa của bạn là ~100%~. Hãy chọn một số đĩa để bắn sao cho tổng điểm thu được là lớn nhất.

Input

Vào từ tệp văn bản GAME.INP:

• Dòng đầu tiên chứa số nguyên dương ~N~ (~1 \leq N \leq 10^6~).
• Dòng thứ hai chứa ~N~ số nguyên ~a_i~ (~1 \leq a_i \leq 10^9~), là số điểm ghi trên các đĩa.

Output

Đưa ra tệp văn bản GAME.OUT một số nguyên là tổng điểm lớn nhất mà người chơi có thể đạt được.

Ví dụ

Sample Input

4
9 3 5 4

Sample Output

18

Giới hạn

• ~1 \leq N \leq 10^6~
• ~1 \leq a_i \leq 10^9~

Ghi chú

• Có ~40%~ số test tương ứng với ~40%~ số điểm của bài có ~1 \leq N \leq 20~.

Nguồn: đề thi trong file PDF (trang 2–3).