Cho mảng A có N số nguyên không âm. Dũng định nghĩa hàm xử lý xâu đẹp của một chuỗi con S có kích thước 3 là từ mảng A như sau

function calculate_beauty(a, b, c):
    mean = (a + b + c) / 3.0    
    array = [a, b, c]    
    sort(array)  
    median = array[1]
    return 3 * abs(mean - median)

Trong đó:

• mean là trung bình của chuỗi con S.
• median là trung vị (điểm giữa) của chuỗi con S.

Yêu cầu:

tìm chuỗi con 𝑆 có kích thước là 3 từ mảng 𝐴 sao cho độ đẹp của 𝑆 là có giá trị nhỏ nhất thông công thức trên.

Đầu vào:

từ thiết bị chuẩn gồm

• Dòng thứ nhất chứa một số nguyên N (số phần tử của mảng). 3≤N≤5000
• Dòng tiếp theo chứa N số nguyên, các phần tử của mảng A. 0≤ A_i≤10^9

Đầu ra:

in ra thiết bị chuẩn độ đẹp tối thiểu của bất kỳ chuỗi con nào có độ dài 3 từ mảng A

Ví dụ:

Input 1

4
1 6 8 0

Output 1

3

Input 2

10
5 5 7 0 1 0 4 7 9 4

Output 2

0

Giải thích:

Input 1:

Với mảng [1, 6, 8, 0] đã cho, Dũng sẽ chọn dãy con [1, 6, 8] sao cho đẹp nhất.

• Trung bình của dãy con sẽ là (1+6+8) /3 = 5
• Trung vị của dãy con sẽ là 6 (vì nó là phần tử ở giữa sau khi sắp xếp dãy con).
• Độ đẹp của dãy con là 3 abs (5-6) = 3.

Input 2:

Với mảng [5, 5, 7, 0, 1, 0, 4, 7, 9, 4] Dũng sẽ chọn dãy con [1, 4, 7] sao cho đẹp nhất.

• Trung bình của dãy con sẽ là (1+4+7) /3 = 4
• Trung vị của dãy con sẽ là 4 (vì nó là phần tử ở giữa sau khi sắp xếp dãy con).
• Độ đẹp của dãy con là 3 abs (4-4) = 0.