Nhà giả kim số học

Ở một vùng đất xa xôi, nơi những con số có linh hồn riêng, một nhà giả kim số học tên Linh đã phát minh ra một trò chơi trí tuệ với tên gọi Hợp Nhất Vô Cực.

Linh tạo ra một bảng chứa \(N\) số nguyên dương, được viết thẳng hàng trên mặt phẳng ma thuật. Mỗi số trong bảng mang một nguồn năng lượng đặc biệt, và khi hai số giống nhau đứng cạnh nhau, Linh có thể kết hợp chúng thành một số mới, lớn hơn hai số ban đầu một đơn vị.

Sau khi kết hợp, hai viên đá cũ biến mất, và thay vào ngay điểm đó bằng viên đá mới. Mục tiêu của Linh là kết hợp sao cho, số lớn nhất trên các viên đá trên dãy là lớn nhất.

Input

• Dòng đầu tiên chứa số nguyên \(N\) \((1 \leq N \leq 10^5)\) - số lượng các số trong bảng.
• Dòng thứ hai chứa \(N\) số nguyên dương, mỗi số không vượt quá \(40\) - các số trên bảng.

Output

• Ghi ra một số nguyên duy nhất - số lớn nhất có thể đạt được sau khi thực hiện các phép hợp nhất tối ưu.

Example

3
1 1 2

3

Scoring

• Với \(30\%\) số test, \(N \leq 1000\).
• Với \(70\%\) số test còn lại, không có ràng buộc gì thêm.