Huy có \(N\) gói kẹo, gói kẹo thứ \(i\) có số lượng viên kẹo là \(a_i\). Số lượng viên kẹo có trong gói có thể giống nhau hoặc khác nhau và các gói kẹo được xếp thành một hàng.

Huy có thể thực hiện không lần hoặc một số lần thao tác như sau:

• Nếu có hai gói kẹo liền kề có số viên kẹo trong mỗi gói bằng nhau, Huy có thể gộp chúng lại thành một gói kẹo mới. Số viên kẹo của gói mới này là tổng số viên kẹo của cả hai gói cũ và chiếm vị trí của chúng.

• Nếu có hai gói kẹo mà số viên kẹo trong mỗi gói bằng nhau và giữa hai gói này chỉ có đúng một gói kẹo, Huy cũng có thể gộp ba gói kẹo này lại thành một gói kẹo mới. Số viên kẹo của gói mới này là tổng số viên kẹo của ba gói bị gộp lại và gói mới này cũng chiếm vị trí của cả ba gói cũ.

Yêu cầu: Giả sử Huy biết cách thực hiện thao tác một cách tối ưu để có được gói kẹo với số viên kẹo trong gói là lớn nhất. Bạn hãy xác định số viên kẹo trong gói đó.

Dữ liệu

• Dòng 1: Số nguyên \(N (1≤ N≤ 400);\)

• Dòng 2: Ghi dãy gồm \(N\) số nguyên dương \(a_1,a_2,…,a_N, (1≤a_i≤10^9,∀i=1,2,..,N).\)

Kết quả

• In ra một số nguyên duy nhất là kết quả tìm được.

Ràng buộc

• Subtask 1: 10% số test với \(N≤4\)

• Subtask 2: 15% \(N≤10\)

• Subtask 3:25% \(N≤50\)

• Subtask 4: 50% Không có ràng buộc bổ sung

Sample Input

7
47 12 12 3 9 9 3

Sample Output

48

Giải thích:

• Gộp hai gói có số viên kẹo là 12 lại, thu được một gói kẹo mới với số viên kẹo là 24, dãy trở thành {47;24;3;9;9;3};

• Tiếp theo, gộp hai gói có số viên kẹo là 9 lại, thu được một gói kẹo mới với 18 viên kẹo, dãy trở thành {47;24;3;18;3};

• Gộp ba gói có số viên kẹo là 3, 18 và 3 lại, thu được một gói mới với 24 viên kẹo, dãy trở thành {47;24;24};

• Cuối cùng, gộp hai gói có số viên kẹo là 24 lại, thu được một gói với với 48 viên, dãy trở thành {47;48};