Trò chơi với băng số là trò chơi tham gia trúng thưởng được mộ tả như sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương ai, i = 1, 2, ...., n. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một sô lượng tuỳ ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô 11, 12, ..., ik. Khi đó điểm số mà người chơi đạt được sẽ là:

Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi.

Dữ liệu: Vào từ file văn bản LINEGAME.INP:

Dòng đầu tiên chứa số nguyên dương n (n ≤ 10^6) là số lượng ô của băng số;

Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an (ai ≤ 10^4, i = 1,2, ..., n) ghi trên băng số.

Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách.

Kết quả: Đưa ra file văn bản LINEGAME.OUT một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi.

Input:

7
4 9 2 4 1 3 7

Output:

17

Ràng buộc: 60% số tests ứng với 60% số điểm của bài có 1 ≤ n ≤ 20.