Cho một chuỗi ~a~ gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Một chuỗi con của ~a~ là chuỗi ~a_i, a_{i+1}, \dots, a_j~ (~1 \le i \le j \le 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.

Input

• Dòng đầu chứa một số nguyên dương ~n \le 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.

Output

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