Cho dãy số nguyên ~a_1,a_2,\ldots,a_n~. Với ba chỉ số ~j<i<k~, năng lượng của bộ ba được tính bởi:</p>

~Q = a_j a_i - a_i^2 - a_j a_k + a_i a_k~.

Yêu cầu

Tìm giá trị ~Q~ lớn nhất.

Input

Dòng đầu chứa số nguyên dương ~n~.

Dòng thứ hai chứa ~n~ số nguyên ~a_i~.

Output

In ra giá trị năng lượng lớn nhất.

Subtask

• 100% số điểm: ~3 \le n \le 10^6~, ~|a_i| \le 10^9~.

Ví dụ

5
1 5 2 6 3

12