Cho một mảng gồm \(n\) phần tử. Coi mảng này là một mảng vòng tròn (tức là phần tử đứng sau \(a_n\) là \(a_1\)). Nhiệm vụ của bạn là sắp xếp lại các phần tử trong mảng sao cho tổng giá trị tuyệt đối của hiệu giữa các phần tử liên tiếp là lớn nhất.

Cụ thể, hãy tìm giá trị lớn nhất của biểu thức:
\(|a_1 - a_2| + |a_2 - a_3| + \dots + |a_{n-1} - a_n| + |a_n - a_1|\)

Input

• Dòng đầu tiên chứa số nguyên dương \(n\).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) cách nhau bởi dấu cách.

Output

• Một số nguyên duy nhất là tổng lớn nhất tìm được.

Constraints

• \(2 \le n \le 10^5\)
• \(1 \le a_i \le 10^9\)

Example

4
4 2 1 8

18

3
10 12 15

10