Safe Lock

Time limit1sMemory limit128 MB

Summary

Given N positions on a circular ring of size 10,000,000, find the minimum total distance to move all points to a common position, minimizing sum of circular distances.

Level: Medium5 of 10
Topics: Sorting, Prefix sum, Greedy, Math
Solved: No attempts yet

Problem

Mirko wants to open a small safe. Its lock is made of N identical discs. Each disc is divided into 10,000,000 equal segments, numbered from 1 to 10,000,000 clockwise. At the start, segments that share the same number on different discs lie exactly one above another.

Each disc is missing exactly one segment; this missing segment is called a hole.

To unlock the safe, every hole must be at the same segment number, i.e. all holes must be aligned one above another.

In one second Mirko can rotate a single disc by one segment, either clockwise or counterclockwise. Because each disc is circular, segment 1 and segment 10,000,000 are neighbours.

Determine the minimum time, in seconds, needed to align all the holes.

Input

The first line contains an integer N (2 ≤ N ≤ 100,000), the number of discs.

Each of the next N lines describes the initial position of one hole. The (i+1)-th line contains an integer P_i (1 ≤ P_i ≤ 10,000,000), the position of the hole on the i-th disc.

Output

Print a single line with the minimum time, in seconds, needed to align all the holes.

Note: the answer can be very large, so mind the size of the data type (use 64-bit integers).

Examples3

Example 1
Input
```
3
5
17
7
```
Expected output
```
12
```
Example 2
Input
```
4
9999999
7
16
9999995
```
Expected output
```
29
```
Example 3
Input
```
4
1
2500001
5000000
7500002
```
Expected output
```
9999998
```