Năng lượng

Điểm: 0,50 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

25-26 TS10 DANANG

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Java, Javascript, Kotlin, Pascal, Python, Scratch

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 = x y - y^{2} - x z + y z$ . 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 \leq i < j < k \leq 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 \leq n \leq 10^{6}$ ).
Dòng thứ hai chứa dãy gồm $n$ số nguyên $a_{1}, a_{2}, . . ., a_{n}$ ( $| a_{i} | \leq 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 \leq n \leq 10^{6}$
$| a_{i} | \leq 10^{6}$
40% số test có $n \leq 100$
30% số test có $n \leq 10^{4}$
30% số test không giới hạn gì thêm.

Ví dụ

Input	Output	Giải thích
7 -5 12 4 20 5 9 3	144

Bình luận

Không có bình luận tại thời điểm này.