Mật khẩu mạng wifi – Quảng Ninh 2023-2024

Đề bài

Mật khẩu đăng nhập mạng wifi của công ty mà Trung đang làm việc được xác định qua bài toán sau. Cho $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ . Hãy tìm 4 chỉ số khác nhau $i, j, k, l$ ( $1 \le i, j, k, l \le n$ ) sao cho $a_i - a_j \times a_k - a_l)$ là lớn nhất. Giá trị lớn nhất đó là mật khẩu mạng wifi mà Trung cần tìm.

Tuy nhiên Trung lại không giỏi toán, nên Trung nhờ bạn tìm mật khẩu mạng wifi.

Dữ liệu vàopass.inp

Vào từ tệp văn bản pass.inp. Dòng thứ nhất chứa một số nguyên $n$ ( $4 \le n \le 10^5$ ). Dòng thứ hai chứa $n$ số nguyên dương $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 10^9$ ).

Kết quả rapass.out

Ghi ra tệp văn bản pass.out một số nguyên là mật khẩu mạng wifi.

Ràng buộc

Có 30% số test ứng với 30% số điểm thỏa mãn: $4 \le n \le 50$ ;
30% số test khác ứng với 30% số điểm thỏa mãn: $4 \le n \le 1000$ ;
40% số test còn lại ứng với 40% số điểm thỏa mãn: Không có thêm ràng buộc nào.

Ví dụ

Ví dụ 1

Dữ liệu vàopass.inp

5
1 3 5 7 9

Kết quả rapass.out

Giải thích

Trong ví dụ 1 chọn $i = 5, j = 2, k = 4, l = 1$ sẽ được $(a_i - a_j) \times (a_k - a_l) = (9 - 3) \times (7 - 1) = 36$ lớn nhất.

Ví dụ 2

Dữ liệu vàopass.inp

10
2 8 7 4 10 5 1 3 3 6

Kết quả rapass.out

Giải thích

Trong ví dụ 2 chọn $i = 2, j = 7, k = 5, l = 1$ sẽ được $(a_i - a_j) \times (a_k - a_l) = (8 - 1) \times (10 - 2) = 56$ lớn nhất.