Vào một ngày đẹp trời, trường X đã tổ chức một cuộc chạy tiếp sức tại hội thao kỷ niệm thành lập trường. Có rất nhiều lớp tham gia vào cuộc đua này, và ai ai cũng muốn giành chiến thắng.

Mỗi đội sẽ có một huấn luyện viên để luyện tập cũng như xếp đội hình để chạy tiếp sức. Và cô giáo Y được bổ nhiệm làm huấn luyện viên của lớp Z. Lớp Z có ~n~ học sinh tham gia vào cuộc đua. Họ sẽ chạy lần lượt trong cuộc đua, người thứ ~i~ có tốc độ là ~s_i~.

Sự khác biệt ~d_i~ ở giai đoạn thứ ~i~ là sự khác biệt giữa tốc độ chạy tối đa và tốc độ chạy tối thiểu giữa ~i~ thành viên đầu tiên đã tham gia cuộc đua.

Nói cách khác, nếu ~a_i~ thể hiện tốc độ của thành viên thứ ~i~ đã tham gia cuộc đua, thì ~d_i = \max(a_1, a_2, \dots, a_i) - \min(a_1, a_2, \dots, a_i)~.

Cô giáo Y tính được rằng, khả năng đoạt giải nhất càng lớn khi tổng ~d_1 + d_2 + \dots + d_n~ đạt giá trị nhỏ nhất. Để có thể làm giảm tổng ~d_1 + d_2 + \dots + d_n~, cô giáo sẽ thay đổi thứ tự chạy của các thành viên.

Input

• Dữ liệu được đọc từ file văn bản CAU4.INP.
• Dòng thứ nhất: Gồm một số nguyên ~n~ ~(1 \leq n \leq 2000)~ – là số thành viên tham gia cuộc đua.
• Dòng thứ hai: Gồm ~n~ số nguyên ~s_1, s_2, \dots, s_n~ ~(1 \leq s_i \leq 10^9)~ – là tốc độ chạy của các thành viên.

Output

• Ghi kết quả ra file văn bản CAU4.OUT.

Scoring

Example input 1

3
3 1 2

Example output 1

3

Example input 2

1
5

Example output 2

0

Example input 3

6
1 6 3 3 6 3

Example output 3

11

Example input 4

3
10 5 6 9 13

Example output 4

27