Năng lượng

Trong chuyến tham gia lắp đặt trạm tín hiệu vệ tinh cho dự án thành phố thông minh của thành phố Đà Nẵng, An là một thành viên của Câu lạc bộ Sáng tạo trẻ thành phố, nhận thấy độ chênh lệch nhiệt độ tại khu vực đỉnh Bà Nà vào các thời điểm sáng, trưa, tối là rất lớn.

Trong nghiên cứu gần đây của mình, An đã phát triển một hệ thống điện mới 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$ đơn vị điện năng theo công thức $Q=xy-y^2-xz+yz$. An thấy rằng Bà Nà là nơi lí tưởng để đưa hệ thống điện mới phục vụ trạm tín hiệu vệ tinh.

Theo khảo sát và ghi nhận tại Bà Nà có $n$ thời điểm thay đổi nhiệt độ khác nhau trong ngày. Hệ thống điện sẽ lấy nhiệt độ tại $3$ thời điểm khác nhau trong $n$ thời điểm đó để tạo ra năng lượng hoạt động cho trạm tín hiệu.

Cho dãy số nguyên $a_1,a_2,...,a_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=a_i$, $y=a_j$ và $z=a_k$ sao cho năng lượng điện tạo ra là lớn nhất.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên $n$ ($3\le n\le {10}^6$).
• Dòng thứ hai chứa dãy gồm $n$ số nguyên $a_1,a_2,...,a_n$ ($|a_i|\le {10}^6$).

Dữ liệu ra

Một số nguyên là năng lượng điện lớn nhất tạo được.

Ràng buộc

• $3\le n\le {10}^6$
• $|a_i|\le {10}^6$
• 40% số test có $n\le 100$
• 30% số test có $n\le {10}^4$
• 30% số test không giới hạn gì thêm.

Ví dụ