Chọn đồ chơi

Bạn Bi rất yêu thích việc mua sắm những đồ chơi khoa học viễn tưởng hiếm và đắt. Cậu ấy giữ chúng theo một dãy theo thứ tự ngày mua và để trong một cái tủ. Vì vậy, bạn Bo sẽ không bao giờ lấy được đồ chơi của cậu ấy. Nhưng vì một lần không may mắn, Bi đã thua Bo trong một vụ cá cược. Và Bo đã yêu cầu Bi chia sẻ đồ chơi. Bởi vì Bi không muốn mất nhiều tiền nên cậu ấy đã quyết định dựa trên một chiến lược để giảm thiểu sự mất mát xuống thấp nhất.

Bi bắt đầu chọn từ đồ chơi đầu tiên ở trong tủ, sẽ lấy một số đồ chơi, gọi là $X$ đồ chơi. Bo sau đó sẽ chọn $X$ đồ chơi (chú ý là Bo sẽ chọn số đồ chơi bằng với Bi, trừ khi số đồ chơi còn lại nhỏ hơn $X$). Việc này sẽ tiếp tục cho đến khi không còn lại đồ chơi nào nữa.

Cụ thể, hai bạn luôn lấy các đồ chơi theo đúng thứ tự trong dãy. Ở mỗi lượt của mình, Bi chọn một giá trị $X\in \{1,2,3\}$ (giá trị $X$ ở các lượt khác nhau có thể khác nhau) và lấy $X$ đồ chơi tiếp theo; sau đó Bo lấy $X$ đồ chơi tiếp theo. Nếu số đồ chơi còn lại ít hơn số cần lấy thì người đang lấy lấy hết số đồ chơi còn lại.

Bạn được đưa cho một dãy của đồ chơi với giá của chúng. Hãy đưa ra số tiền lớn nhất Bi có thể giữ lại ứng với số đồ chơi mà Bi chọn. Bi chỉ có thể chọn $1$, $2$ hay $3$ đồ chơi ($X$ có giá trị $1$, $2$ hay $3$).

Yêu cầu: Tính tổng số tiền lớn nhất của các đồ chơi mà bạn Bi chọn.

Dữ liệu vào

• Dòng đầu tiên ghi số nguyên dương $N$ là số đồ chơi.
• Dòng thứ hai ghi $N$ số nguyên dương là giá tiền của các đồ chơi theo thứ tự trong tủ, các số cách nhau bởi một dấu cách.

Dữ liệu ra

Ghi ra một số nguyên duy nhất là tổng số tiền lớn nhất của các đồ chơi mà bạn Bi chọn.

Ràng buộc

• $1\le N\le {10}^5$.
• $1\le$ giá tiền của mỗi đồ chơi $\le {10}^7$.

Subtasks

• Subtask 1 ($30\%$ số điểm): $N\le 100$, giá tiền các đồ chơi $\le {10}^3$.
• Subtask 2 ($30\%$ số điểm): $N\le {10}^3$, giá tiền các đồ chơi $\le {10}^5$.
• Subtask 3 ($40\%$ số điểm): không có ràng buộc gì thêm.

Ví dụ