G. Teleporting through Kazakhstan
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The ICPC World Finals in Astana are around the corner, and your team has prepared a list of must-visit places! Your journey starts at your home and spans several key cities and touristic spots across the vast and beautiful landscapes of Kazakhstan before reaching the competition venue in Astana. Along the way, you will pass through several key stops (positions) you must visit, including the bustling city of Almaty, the historical city of Shymkent, and the scenic wonders near Karaganda.

The ICPC, aware that competitors have many places to visit, has created a special teleportation device to help teams complete their touristic duties on time for the competition. You can either travel to the next stop normally or use the special teleportation device. Each time you use a teleport, it is destroyed, and a new teleport point is created at your last stop before teleporting.

To simplify the planning, consider that your home and the first teleport is at point 0 and the touristic spots are arranged in a line. The cost of normal travel is the absolute difference in distance between your current stop and the next stop. The cost of a teleport is the absolute difference in distance between your last teleport position and the next stop.

Your task is to determine the minimum total travel cost to reach the competition venue in Astana from your home using the teleportation device. Note that your teammates put a lot of care and effort into crafting this itinerary and want to visit the touristic spots in order.

Input

The first line contains a positive integer $$$n (1 \leq n \leq 1000)$$$, the number of spots.

The next line contains $$$n$$$ space separated positive integers $$$a_i (1 \leq a_i \leq 10^9)$$$, the coordinates of the touristic spots.

Output

A single number, the minimum total distance traveled to visit all spots in order.

Examples
Input
3
10 4 12
Output
16
Input
7
1 2 1 1 2 2 1
Output
3
Note

The solution to the first instance proceeds as follows:

  • team and teleport start at point at coordinate 0;
  • team visits point at coordinate 10 (+10);
  • team teleports to point at coordinate 0 (0+);
  • (A teleport is created at point 10 and the one at point 0 is destroyed);
  • team visits point at coordinate 4 (+4);
  • team teleports to point at coordinate 10 (0+);
  • (A teleport is created at point 4 and the one at point 10 is destroyed);
  • team visits point at coordinate 12 (+2).