Có \(n\) người tham gia một cuộc thi. Người thứ \(i\) có chỉ số sức mạnh là \(a_i\). Ban tổ chức muốn thực hiện ghép hai người thành một đội để thu được \(\lfloor\frac{n}{2}\rfloor\) đội thi (nếu \(n\) lẻ thì sẽ có một người bị loại) sao cho chênh lệch sức mạnh tối đa của hai đội bất kỳ là nhỏ nhất. Biết rằng, chỉ số sức mạnh của một đội gồm hai người \((u, v)\) sẽ là \(a_u + a_v\). Hãy giúp ban tổ chức tìm ra cách ghép tối ưu.

Input

• Dòng đầu tiên gồm một số nguyên dương \(n \le 3 \times 10^5\) – số người trong cuộc thi.
• Dòng tiếp theo gồm \(n\) số nguyên \(0 \le a_i \le 10^9\).

Output

• Một dòng duy nhất gồm chênh lệch sức mạnh nhỏ nhất có thể thu được.

Example

6
1 1 1 2 2 3

1

Scoring

• Subtask 1 (\(30\%\) số điểm): \(n\) chẵn.
• Subtask 2 (\(30\%\) số điểm): \(n \le 1000\) và \(n\) lẻ.
• Subtask 3 (\(20\%\) số điểm): \(a_i \le 1\).
• Subtask 4 (\(20\%\) số điểm): \(n\) lẻ.