Cho một chuỗi A gồm N số nguyên A1, . . . , An. Một chuỗi con của A là chuỗi Ai A(i+1) . . . Aj với 1 ≤ i ≤ j ≤ N, và độ dài của chuỗi con này bằng j − i + 1. Một phép xoá trên chuỗi là việc chọn một chuỗi con trong chuỗi và xóa nó đi, thu được một chuỗi mới gồm n − j + i − 1 phần tử còn lại. Với mỗi phép xoá, độ dài của chuỗi con được chọn phải là lũy thừa của 2 và trong tất cả các phép xoá được thực hiện trên chuỗi A, độ dài của các chuỗi đã xóa phải đôi một khác nhau. Giá trị của mỗi chuỗi mới thu được được tính bằng giá trị lớn nhất trong các tổng các phần tử của một chuỗi con của nó trong trường hợp chuỗi chứa ít nhất một tổng dương, nếu không giá trị của chuỗi bằng 0.

Yêu cầu: Cho phép thực hiện nhiều lần phép xoá trên chuỗi A, hãy xác định giá trị lớn nhất có thể của chuỗi.

Dữ liệu:

• Dòng đầu chứa một số nguyên dương N ≤ 1000;

• Dòng thứ hai chứa N số nguyên là giá trị các phần tử của chuỗi A nằm trong khoảng [10^(-6), 10^6], hai số liên tiếp được ghi cách nhau bởi dấu cách.

Kết quả

Ghi ra duy nhất một số nguyên là giá trị lớn nhất của chuỗi thu được.

Sample Input

14
13 -19 13 -5 -12 11 20 4 -10 1 -7 19
-19 3

Output

76

Hạn chế

ˆ Subtask 1: N ≤ 30;
ˆ Subtask 2: luôn tồn tại một giải pháp với nhiều nhất một phép xoá;
ˆ Subtask 3: luôn tồn tại một giải pháp với nhiều nhất hai phép xoá;
ˆ Subtask 4: không có ràng buộc gì thêm.