Overview

Place cities as points on a straight line, and construct a communication network such that removing any single city still leaves the remaining cities connected.
The minimum cost is twice the distance between the westernmost and easternmost cities, namely \(2(\max X_i - \min X_i)\).

Analysis

Arrange the city positions from west to east as:

\(Y_1 < Y_2 < \cdots < Y_N\)

To state the conclusion first, the optimal communication network can be constructed as follows:

• Connect adjacent cities to each other
• Additionally, connect the westernmost city \(Y_1\) and the easternmost city \(Y_N\)

In other words, form a “cycle” that goes around all cities in their order on the line.

The cost in this case is:

\[(Y_2 - Y_1) + (Y_3 - Y_2) + \cdots + (Y_N - Y_{N-1}) + (Y_N - Y_1)\]

The sum of adjacent city distances in the first part is:

\[Y_N - Y_1\]

So the total is:

\[2(Y_N - Y_1)\]

For example, if the city positions are \(0, 4, 10\):

• Connect \(0\) and \(4\): cost \(4\)
• Connect \(4\) and \(10\): cost \(6\)
• Connect \(0\) and \(10\): cost \(10\)

The total is \(20 = 2(10 - 0)\).

Since this structure is a cycle, removing any single city still leaves the remaining cities connected like a path.

---

Now, why can’t we do better than this?

Consider a “cut” between adjacent positions \(Y_k\) and \(Y_{k+1}\).

This divides the cities into the set west of the cut and the set east of the cut.

Suppose there is only \(1\) communication line crossing this cut.
If we remove the city that is an endpoint of that single line, there would be no line connecting the west side and the east side, and the network would be disconnected.

Therefore, to satisfy the condition, every cut must have at least \(2\) communication lines crossing it.

The cost of each communication line equals the sum of the lengths of the cuts it crosses.
Thus, since every cut is counted at least \(2\) times in the cost, the total cost is at least:

\[2\{(Y_2 - Y_1) + (Y_3 - Y_2) + \cdots + (Y_N - Y_{N-1})\}\]

This equals:

\[2(Y_N - Y_1)\]

In summary:

• At least \(2(Y_N - Y_1)\) is always required
• We can actually construct a network with cost \(2(Y_N - Y_1)\)

So the answer is:

\[2(\max X_i - \min X_i)\]

If we naively consider communication lines between all pairs of cities, there are \(O(N^2)\) of them, which is far too slow for \(N \leq 10^6\).
However, from the analysis above, we only need the minimum and maximum positions.

Algorithm

Given the city positions \(X_i\):

1. Find the minimum value \(\min X_i\)
2. Find the maximum value \(\max X_i\)
3. Output \(2(\max X_i - \min X_i)\)

There is no need to sort the cities.

Complexity

• Time complexity: \(O(N)\)
• Space complexity: \(O(1)\)

Implementation Notes

The answer is determined solely by the minimum and maximum values.

Since the given \(N\) can be as large as \(10^6\), it is safe to perform input processing efficiently.
In the provided code, the entire input is read as a byte array and integers are parsed manually.

Also, the first integer that appears is \(N\), so it is excluded from the min/max calculation.

Source Code

import sys

data = sys.stdin.buffer.read()
mn = 10**18
mx = -1
num = 0
in_num = False
idx = 0

for c in data:
    if 48 <= c <= 57:
        num = num * 10 + (c - 48)
        in_num = True
    else:
        if in_num:
            if idx > 0:
                if num < mn:
                    mn = num
                if num > mx:
                    mx = num
            idx += 1
            num = 0
            in_num = False

if in_num and idx > 0:
    if num < mn:
        mn = num
    if num > mx:
        mx = num

print((mx - mn) * 2)

---

This editorial was generated by gpt-5.5-high.