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.

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.

Input

• Dòng đầu tiên ghi số nguyên dương ~N~ là số đồ chơi.
• ~N~ dòng tiếp theo ghi ~N~ số nguyên dương là giá tiền của các đồ chơi.
• Các số trên một dòng ghi cách nhau bởi một dấu cách.

Output

• 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.

Sample Input 1

4
5 4 3 2

Sample Output 1

12