Cho một dãy gồm số nguyên dương. Ta thực hiện một quy trình rút gọn dãy này bằng cách lặp lại thao tác sau cho đến khi dãy chỉ còn đúng một phần tử:
- Chọn hai phần tử bất kỳ và đang có trong dãy.
- Xóa và .
- Thêm một phần tử mới có giá trị bằng vào dãy.
Gọi là giá trị lớn nhất có thể đạt được.
Gọi là giá trị nhỏ nhất có thể đạt được.
Hãy tính hiệu số .
Dữ liệu:
- Dòng đầu tiên chứa một số nguyên dương .
- dòng tiếp theo, mỗi dòng chứa một số nguyên dương.
- Dòng tiếp theo chứa số , biểu thị kết thúc dữ liệu nhập.
Kết quả:
- Xuất ra duy nhất một số nguyên là giá trị tìm được.
Ví dụ:
Dữ liệu:
Kết quả:
Giải thích:
- Để tìm : Kết hợp (1, 2) . Tập còn {3, 3}. Kết hợp (3, 3) .
- Để tìm : Kết hợp (2, 3) . Tập còn {1, 7}. Kết hợp (1, 7) .
- Kết quả
Giới hạn:
- .
- Đảm bảo mọi kết quả tính toán trung gian và kết quả cuối cùng đều nằm trong phạm vi của số nguyên có dấu 32-bit.
