Một thiết bị thí nghiệm nhận vào ba mức nhiệt độ ~x, y, z~ theo đúng thứ tự đó và sinh ra năng lượng

~Q = (x - y) \times (y - z)~

đơn vị. Trong một ngày, thiết bị chỉ đo được nhiệt độ ở ba thời điểm. Ta có dãy nhiệt độ ~t_1, t_2, \dots, t_n~ ghi tại ~n~ thời điểm trong ngày, xếp theo thứ tự thời gian.

Hãy chọn ba chỉ số ~i, j, k~ với ~1 \le i < j < k \le n~, đặt ~x = t_i~, ~y = t_j~, ~z = t_k~, sao cho năng lượng ~Q~ lớn nhất có thể. In ra giá trị lớn nhất đó.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~n~ (~3 \le n \le 10^6~), số thời điểm đo.
• Dòng thứ hai chứa ~n~ số nguyên ~t_1, t_2, \dots, t_n~ (~|t_i| \le 10^6~), nhiệt độ tại các thời điểm theo thứ tự thời gian.

Kết quả

• In ra một dòng chứa một số nguyên duy nhất là năng lượng lớn nhất tạo được.

Ví dụ

MAXENERGY.INP

7
9 12 4 7 5 9 3

MAXENERGY.OUT

20

Giải thích: Chọn ~x = 12~, ~y = 7~, ~z = 3~ thì ~Q = (12 - 7) \times (7 - 3) = 20~, và không có bộ ba nào cho kết quả lớn hơn.

Giới hạn

• Subtask 1 (50% số điểm): ~n \le 100~.
• Subtask 2 (30% số điểm): ~n \le 5 \times 10^3~.
• Subtask 3 (20% số điểm): không có ràng buộc gì thêm.