Cho số nguyên dương $n$ và dãy số nguyên $a_1,a_2,…,a_n$.

Yêu cầu: Tìm $3$ chỉ số $i,j,k$ sao cho $1≤i<j<k≤n$ để $(a_i-a_j )×(a_j-a_k)$ lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên dương $n(3≤n≤10^6 ).$

• Dòng thứ hai chứa $n$ số nguyên dương $a_1,a_2,…,a_n (|a_i |≤10^6 ).$

Output

• Ghi một số là giá trị $(a_i-a_j )×(a_j-a_k)$ lớn nhất tìm được.

Ràng buộc

• Subtask 1: 50% test $n≤100.$

• Subtask 2: 30% test $n≤5×10^3.$

• Subtask 3: 20% test $n≤10^6.$

Sample Input

7
9 12 4 7 5 9 3

Sample Output

20