MAXENERGY Máy nhiệt năng

XZONE là một vùng đất vô cùng khắc nghiệt khi nhiệt độ trong ngày liên tục thay đổi và có  dộ biến thiên rất  rộng. Không một sinh vật nào có thể sinh sống được ở vùng đất này, vì vậy  XZONE bị lãng quên trong một thời gian rất dài.

Trong nghiên cứu gần đây của mình, Bờm phát minh một hệ thống  nhiệt năng 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 = (x – y) × (y – z) đơn vị năng lượng. Bờm nhận thấy rằng XZONE    là nơi lý tưởng để thử nghiệm phát minh của mình.

Bờm khảo sát và ghi nhận XZONE có n thời điểm thay đổi  nhiệt  độ khác nhau trong ngày.  Vì là phiên bản thử nghiệm nên hệ thống chỉ có thể thu nhiệt tại 3 thời điểm ở mỗi ngày. Bờm tính toán các thời điểm thu nhiệt sao cho năng lượng tạo ra là lớn nhất.

Yêu cầu: cho dãy số nguyên t₁, t₂, …, t_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 ≤ i < j < k ≤ n) để thu 3 mức nhiệt x = t_i, y = t_j và z = t_k sao cho năng lượng tạo ra là lớn nhất.

Input

• Dòng đầu tiên chứ số nguyên n (3 ≤ n ≤ 10⁶)
• Dòng tiếp theo chứa dãy gồm n số nguyên t₁, t₂, …, t_n (|t_i| ≤ 10⁶)

Output: ghi một số nguyên là năng lượng lớn nhất tạo được.