Developers of a new amusement park want to build a roller coaster. They believe that people get more enjoyment from the ride if there is a larger height difference between adjacent sections. However, the supply team has already purchased $N$ supports, whose heights are known. Help the park developers arrange the supports in a line in such an order that the sum of the height differences between all adjacent supports is maximized (the height difference is defined as the absolute difference between the heights of two adjacent supports).

Input

The first line contains a single integer $N$, $2 \leqslant N \leqslant 10^5$, the number of supports. The next line contains $N$ non-negative integers separated by spaces, each not exceeding $10^8$, representing the heights of the purchased supports.

Output

A single non-negative integer — the maximum possible sum of height differences.

Examples

Input 1

4
10 20 1 1000

Output 1

2008