Ba bạn nhỏ Miu Bin Bon cùng nhau chơi một trò chơi. Các bạn chọn ra n chiếc thẻ để trong một chiếc hộp mà muốn lấy tấm thẻ dưới thì buộc phải lấy các tấm thể ở trên trước. Mỗi chiếc thẻ có ghi một giá trị đại diện cho sức mạnh của tấm thẻ đó. Xét về mức độ các trò chơi thông minh thì Miu luôn tỏ ra vượt trội Bin và Bon. Vì vậy hai bạn Bin Bon hợp lực lại để đối kháng với bạn Miu. Hai bạn Bin và Bon sẽ lần lượt chọn trước hai tấm thẻ, sau đó đến lượt Miu chọn tấm thẻ thứ 3. Chỉ số sức mạnh của tấm thẻ được cho trong dãy số a1, a2, …an. Hai bạn Bin và Bon muốn chọn sao cho tổng sức mạnh trong hai tấm thẻ của mình lớn hơn sức mạnh của tấm thẻ trong tay cô chị là lớn nhất có thể, nghĩa là nếu gọi sức mạnh tầm thể của Bin là x, sức mạnh trong tấm thẻ của Bon là y sức mạnh trong tấm thẻ của Miu là z thì ta cần chọn sao cho x + y lớn hơn z nhiều nhất có thể. Lưu ý về thứ tự chọn

thể là Bin -> Bon -> Miu

Input Specification

• Dòng đầu ghi số nguyên dương n (0 < n <= 10⁶).

• Dòng 2 ghi số n nguyên dương a1, a2, ..., an (0 <=|a| <= 10⁹)

Output Specification

In ra một số là giá trị lớn nhất của x + y − z