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, An đã 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 là ~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~.

Yêu cầu

Cho dãy số nguyên ~a_1, a_2, \ldots, 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 \le i < j < k \le 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.

Dữ liệu đầu vào

Gồm hai dòng:

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

Dữ liệu đầu ra

Gồm một số nguyên là năng lượng điện lớn nhất tạo được.

Ràng buộc dữ liệu

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

Ví dụ

Ví dụ 1

INPUT

7
-5 12 4 20 5 9 3

OUTPUT

144