Fast Delivery Corporation built one of its offices right in the middle of the longest straight street in Cuba in order to satisfy every order of those customers who live along that street.

The addresses of the houses to which the merchandises are distributed are represented by integer numbers which represent the distance between the office and the corresponding houses. If we consider that the office is located at position 0, then the positive addresses are located to the right of the office, and the negative addresses are located to the left of the office. 

The delivery orders are satisfied in the same order in which they were received.

Fast Delivery Corporation has assigned two employees to the new office. Those employees are in charge of distributing the merchandises. At the beginning of the day, the orders are shared between both employees. 

The corporation wants to share the orders between the two employees in such a way that the total distance required to deliver all the merchandise is minimized.

Input

Line 1: a single integer N (1 <= N <= 100,000) representing the number of orders

The next N lines contain an integer representing an address where a merchandise will be delivered.

The distance between the office and any house is not greater than 10⁸

Output

A single line: the minimum distance the two employees have to travel to satisfy every order.

Example

Input:
 5
1
-1
2
-2
3

Output:
5

Note: The naive greedy doesn't work. Also remember that the deliveries must be satisfied in the same order they appear in the input.