The city of Straight Horn is one straight street. In the city works a company that deals with the delivery of goods. For convenience, delivery addresses are presented in the form of numbers that specify the distance from the office of the company. Positive numbers in one direction, and negative ones in the other. Orders for delivery are performed by the company in sequence, in the order in which they were assigned.

There are two couriers in the company. At the beginning of the working day, orders are distributed between them, and each is sent along its route. Companies need to plan the distribution of orders so that the total distance that will be passed by couriers at the time of the last order will be minimal.

Write a program that, by distances from the company's office, finds the smallest total distance that its employees will go through.

Input

The first line contains an integer n (1 ≤ n ≤ 105) - the number of orders. Each of the next n lines contains one integer - the distance from the office to the addressee. If the distance is positive, then the addressee is in one part of the city relative to the office of the company, and if negative, then in another. Distances do not exceed 108 by absolute value.

Output

Print one integer - the minimum possible total distance that will be passed by both employees of the company.