Các học sinh tham gia đội tuyển thi học sinh giỏi môn Tin học thường chơi game rất giỏi. Vì vậy, trong bài tập này chúng ta hãy giải bài toán trò chơi 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 $02$ viên đạn, mỗi lần bóp cò chỉ bắn ra $01$ viên đạn, sau khi bắn $01$ viên đạn hoặc bắn hết $02$ 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 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 của bạn là lớn nhất.

Yêu cầu: Cho $N$ đĩa có ghi số điểm của đĩa tương ứng. Máy phóng đĩa sẽ phóng lần lượt từ đĩa thứ nhất đến đĩa thứ $N$. Hãy xác định tổng điểm lớn nhất mà người chơi có thể đạt được.

• Dòng đầu tiên chứa số nguyên dương $N\left(1 \leq N \leq 10^{6}\right)$.
• Dòng thứ hai chứa $N$ số nguyên $a_{i}\left(1 \leq a_{i} \leq 10^{9}\right)$, các số cách nhau ít nhất một dấu cách, là số điểm ghi trên các đĩa .

Đưa ra một số nguyên là số điểm lớn nhất mà người chơi có thể đạt được.

Có $40 \%$ số tests ứng với $40 \%$ số điểm của bài có $1 \leq N \leq 20$.

HungTV QHĐ