Trong chuyến tham gia lắp đặt trạm tín hiệu vệ tinh cho dự án thành phố thông minh của thành phố Đà Nẵng, An là một thành viên của Câu lạc bộ Sáng tạo trẻ thành phố, nhận thấy độ chênh lệch nhiệt độ tại khu vực đỉnh Bà Nà vào các thời điểm sáng, trưa, tối là rất lớn.

Trong nghiên cứu gần đây của mình, Anh đã phát triển một hệ thống điện mới dựa trên sự biến đổi kép của nhiệt độ. Khi hệ thống được cung cấp 3 mức nhiệt độ khác nhau theo thứ tự lần lượt x, y, và z thì sẽ tạo ra Q đơn vị điện năng theo công thức \(Q = xy - y^2 - xz + yz\). An thày rằng Bà Nà là nơi lí tưởng để đưa hệ thống điện mới phục vụ trạm tín hiệu vệ tinh.

Theo khảo sát và ghi nhận tại Bà Nà có \(n\) thời điẻm thay đổi nhiệt độ khác nhau trong ngày. Hệ thống điện sẽ lấy nhiệt độ tại 3 thời điểm khác nhau trong \(n\) thời điểm đó để tạo ra năng lượng hoạt động cho trạm tín hiệu.

Yêu cầu: Cho dãy số nguyên \(a_1\), \(a_2\), ..., \(a_n\) là nhiệt độ tại \(n\) thời điểm theo thứ tự thời gian trong một ngày. Hãy tìm 3 thời điểm \(i\), \(j\), \(k\) \((1 \leq i < j < k \leq n)\) để thu 3 mức nhiệt \(x = a_i\), \(y = a_j\) và \(z = a_k\) sao cho năng lượng điện tạo ra là lớn nhất.

Input

Đọc từ file NHIETDO.INP gồm:

• Dòng thứ nhất chứa số nguyên \(n\) \((3 \leq n \leq 10^6)\)
• Dòng thứ hai chứa dãy gồm \(n\) số nguyên \(a_1\), \(a_2\), ..., \(a_n\) \((|a_i| \leq 10^6)\)

Output

Ghi ra file NHIETDO.OUT một số nguyên là năng lượng điện lớn nhất tạo được.

Example

7
-5 12 4 20 5 9 3

144

Ràng buộc

• 40% số test có \(n \leq 100\).
• 30% số test có \(n \leq 10^4\).
• 30% số test không giới hạn gì thêm.