Hiện nay quỹ đất rất hạn hẹp nên con người xây dựng những công xưởng sản xuất ở dưới lòng đất. Công ty VinaHam có một xưởng sản xuất đặt ở dưới lòng đất, có \(n\) công nhân làm việc trong một dây chuyền sản xuất coi như trên một đường thẳng có tọa độ lần lượt là \(x_1, x_2, ...,x_n\). Để tiêt kiệm kinh phí Công ty chỉ xây dựng hai cửa lên xuống. Bạn hãy xác định vị trí xây dựng của 2 cửa này để làm sao tổng khoảng các từ tất cả các vị trí (tọa độ) đến một trong hai cửa là ngắn nhất.

Input

Dòng đầu chứa số nguyên \(n (1 \leq n \leq 10^5)\)

Dòng tiếp theo chứa \(n\) giá trị tương ứng với tọa độ của các nhân viên, các tọa độ có thể trùng nhau \(x_1, x_2, ...,x_n\) có giá trị tuyệt đối không vượt quá 10^9.

Output

Tổng khoảng cách nhỏ nhất được xác định của tất cả các vị trí đến 1 trong 2 cửa lên xuống tới tất cả các vị trí

Ví dụ 1

Input

7
1 2 3 4 15 16 17

Output

6

Giải thích : ta xây dựng cửa một ở vị trí 2 và cửa hai ở vị trí 16

Ví dụ 2

Input

7
4 -9 4 4 4 4 4

Output

0

Giải thích ví dụ 2: Xây cửa thoát hiểm tại tọa độ -9 và 4