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$.