Kevin has a sequence of integers a₁, a₂, ..., a_n. Define the strength of the sequence to be

|a₁ - a₂| + |a₂ - a₃| + ... + |a_n-1 - a_n| + |a_n - a₁|.

Kevin wants to make his sequence stronger, so he reorders his sequence into a new sequence b₁, b₂, ..., b_n. He wants this new sequence to be as strong as possible. What is the largest possible strength of the resulting sequence?

Input

The input consists of 2 lines. The first line has a positive integer n. The second line contains the n integers a₁, a₂, ..., a_n.

Output

Output a single integer: the maximum possible strength.

Constraints

1 <= n <= 10⁵.

|a_i| <= 10⁹. Note that a_i can be negative.