Chiến binh và Cung thủ

Có $n$ vị trí phân biệt nằm trên một trục số, cho bởi các tọa độ $x_1,x_2,\dots ,x_n$ ($n$ luôn là số chẵn). Hai người chơi A và B lần lượt cấm các vị trí, A đi trước. Mỗi lượt, người chơi đến lượt cấm đúng một trong các vị trí còn lại. Họ tiếp tục cho đến khi chỉ còn lại đúng hai vị trí (tức là tổng cộng có $n-2$ lượt cấm).

Sau khi kết thúc, quân của A đứng ở vị trí có tọa độ nhỏ hơn trong hai vị trí còn lại, quân của B đứng ở vị trí có tọa độ lớn hơn. Khoảng cách ban đầu giữa hai quân là hiệu hai tọa độ đó.

A muốn khoảng cách này càng nhỏ càng tốt, còn B muốn nó càng lớn càng tốt. Hãy xác định khoảng cách giữa hai quân khi cả hai người chơi đều chơi tối ưu.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên phân biệt $x_1,x_2,\dots ,x_n$.

Dữ liệu ra

• In ra một số nguyên duy nhất: khoảng cách giữa hai quân khi cả hai chơi tối ưu.

Ràng buộc

• $2\le n\le 2·{10}^5$, $n$ chẵn.
• $0\le x_i\le {10}^9$, các $x_i$ đôi một phân biệt.

Ví dụ