Cho dãy \(n\) số nguyên \(a_1\), \(a_2\), \(a_3\),..., \(a_n\). Bạn được phép áp dụng một số thao tác lên dãy này, mỗi thao tác gồm hai bước:

• Chọn ra hai phần tử kề nhau và bằng nhau trong dãy.
• Xóa đi một trong hai phần tử và tăng phần tử còn lại lên \(2\) đơn vị.

Dễ thấy rằng, sau \(m\ge 0\) lần thực hiện thao tác, dãy số ban đầu sẽ chỉ còn đúng \(n-m\) phần tử. Gọi \(v\) là giá trị lớn nhất trong số \(n-m\) phần tử này. Bạn hãy lập trình tìm cách áp dụng các thao tác đó \(m\) lần tùy ý (\(m=0\) vẫn hợp lệ) sao cho \(v\) đạt được giá trị lớn nhất có thể nhé!

Input

• Dòng đầu chứa số nguyên dương \(n \ge 2\).
• Dòng tiếp theo chứa \(n\) số nguyên dương \(a_1\), \(a_2\),..., \(a_n\) (\(a_i\leq 10^6\) với mọi \(i\)).

Output

• Một số nguyên thể hiện giá trị lớn nhất có thể của phần tử còn lại trong dãy.

Ví dụ

Sample input

4
1 1 1 3

Sample output

5

Giải thích

Ban đầu ta thao tác ở hai phần tử \(1\) tại vị trí thứ nhì và thứ ba để thu được dãy \([1,3,3]\). Tiếp theo ta thao tác ở hai phần tử sau cùng để thu được dãy \([1,5]\). Giá trị tối ưu thu được là \(5\).

Ràng buộc

• Subtask 1 (30% số điểm): \(n\leq 10\).
• Subtask 2 (70% số điểm): \(n\leq 300\).