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ó độ 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) \cdot (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_1, t_2, \dots, 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 \le i < j < k \le 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ứa số nguyên \(n\) (\(3 \le n \le 10^6\)).
• Dòng tiếp theo chứa dãy gồm \(n\) số nguyên \(t_1, t_2, \dots, t_n\) (\(|t_i| \le 10^6\)).

Output

• Ghi một số nguyên duy nhất là năng lượng lớn nhất tạo được.

Example

7
9 12 4 7 5 9 3

20