Delivery#4517
The city of Straight Horn consists of a single straight street. There is a company in the city that delivers goods. For convenience, delivery addresses are represented as numbers, which specify their distance from the company office. Positive numbers are in one direction from the office, negative numbers in the other.
Orders are fulfilled by the company sequentially, in the order they are assigned.
The company employs two couriers. At the start of the working day, orders are distributed between them, and each sets off on their route. The distribution of orders should be planned so that the total distance traveled by the couriers by the time the last order is completed is minimized.
Write a program that, given the distances from the company office, finds the minimum total distance that its employees will travel.
The first line contains an integer (1 \leq n \leq 10^5) — the number of orders. Each of the next lines contains one integer — the distance from the office to the addressee. If the distance is positive, the addressee is in one part of the city relative to the office; if negative, in the other. Distances do not exceed 10^8 by absolute value.
Print a single integer — the minimum total distance that both employees of the company will travel.
Example 1