Overview

This problem asks us to rearrange \(N\) values in any order to maximize the sum of absolute differences between adjacent values.
By sorting the values in ascending order and arranging “small values” and “large values” alternately, we can find the maximum sum using a mathematical formula.

Analysis

Hereafter, we assume the sorted array is:

\( a_0 \leq a_1 \leq \cdots \leq a_{N-1} \)

Trying all permutations would take \(O(N!)\) time, which is far too slow for \(N \leq 10^6\).
Also, a simple greedy approach like “making pairs with the largest differences first” is incorrect because the loss varies depending on which values are placed at the ends.

The key is to observe how each value contributes to the total sum.

When two adjacent values are \(x \leq y\), their contribution is:

\( |x-y| = y-x \)

That is, the larger value contributes \(+1\) to the sum, and the smaller value contributes \(-1\).

Considering a single value:

• A value placed at either end has only one neighbor, so its coefficient is either \(+1\) or \(-1\).
• A value placed in the interior has two neighbors, so its coefficient is \(+2\), \(0\), or \(-2\).

To maximize the sum, we want to assign positive coefficients to large values and negative coefficients to small values.
Therefore, it is basically optimal to:

• Make small values “valleys”
• Make large values “peaks”

and arrange them alternately.

When \(N\) is Even

Let \(N=2m\).

We divide the elements into the smaller half:

\( a_0, a_1, \ldots, a_{m-1} \)

and the larger half:

\( a_m, a_{m+1}, \ldots, a_{2m-1} \)

If we arrange them alternately, the smaller half contributes negatively and the larger half contributes positively.
If all small values could contribute \(-2\) and all large values could contribute \(+2\), the sum would be:

\( 2 \times \left(\sum_{i=m}^{2m-1} a_i - \sum_{i=0}^{m-1} a_i\right) \)

However, in reality, the sequence has two ends, and the values at the ends are adjacent to only one element.
When \(N\) is even, it is optimal to place one value from the smaller half and one value from the larger half at the ends.

To minimize the loss when choosing which values to place at the ends:

• For the smaller half, we should place the largest element \(a_{m-1}\) at the end.
• For the larger half, we should place the smallest element \(a_m\) at the end.

Therefore, the maximum sum is:

\( 2 \times \left(\sum_{i=m}^{2m-1} a_i - \sum_{i=0}^{m-1} a_i\right) - (a_m-a_{m-1}) \)

When \(N\) is Odd

Let \(N=2m+1\).

The median is \(a_m\).
We consider two cases depending on whether we put this median into the “smaller half” or the “larger half”.

1. When \(a_m\) is placed in the smaller half

The smaller half has \(m+1\) elements, and the larger half has \(m\) elements.
If we arrange them alternately, the elements from the smaller half will be at both ends.

Since the values from the smaller half placed at the ends should be as large as possible, we place \(a_{m-1}\) and \(a_m\) at the ends.

In this case, the maximum sum is:

\( 2 \times \left(\sum_{i=m+1}^{2m} a_i - \sum_{i=0}^{m-1} a_i\right) - (a_m-a_{m-1}) \)

2. When \(a_m\) is placed in the larger half

The larger half has \(m+1\) elements, and the smaller half has \(m\) elements.
If we arrange them alternately, the elements from the larger half will be at both ends.

Since the values from the larger half placed at the ends should be as small as possible, we place \(a_m\) and \(a_{m+1}\) at the ends.

In this case, the maximum sum is:

\( 2 \times \left(\sum_{i=m+1}^{2m} a_i - \sum_{i=0}^{m-1} a_i\right) - (a_{m+1}-a_m) \)

Therefore, when \(N\) is odd, the maximum sum is the larger of the two cases above, which is:

\( 2 \times \left(\sum_{i=m+1}^{2m} a_i - \sum_{i=0}^{m-1} a_i\right) - \min(a_m-a_{m-1}, a_{m+1}-a_m) \)

For example, for \([1,2,3,4,5]\):

\( 2 \times ((4+5)-(1+2)) - \min(3-2,4-3) = 12-1=11 \)

Indeed, if we arrange them as \(2,4,1,5,3\), we get:

\( |2-4|+|4-1|+|1-5|+|5-3|=2+3+4+2=11 \)

Algorithm

1. Sort the array \(C\) in ascending order.
2. Let \(m=\lfloor N/2 \rfloor\).
3. Calculate the sum of the smaller half, low.
4. Branch based on whether \(N\) is even or odd.
   • If \(N\) is even:
     $\( \text{ans} = 2 \times \left(\sum_{i=m}^{N-1} a_i - \sum_{i=0}^{m-1} a_i\right) - (a_m-a_{m-1}) \)$
   • If \(N\) is odd:
     $\( \text{ans} = 2 \times \left(\sum_{i=m+1}^{N-1} a_i - \sum_{i=0}^{m-1} a_i\right) - \min(a_m-a_{m-1}, a_{m+1}-a_m) \)$

In the code, we use total to efficiently calculate the required sums.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Dominated by the sorting step.
• Space Complexity: \(O(N)\)
  • Required to store the array.

Implementation Points

• The answer can be up to approximately \(10^{15}\), so long long is required in languages like C++. In Python, integers have arbitrary precision, so this is not an issue.

• When \(N\) is odd, since \(N \geq 3\), a[m-1], a[m], and a[m+1] are guaranteed to exist.

• Since the input size is large, it is safer to use sys.stdin.buffer.readline in Python.

• n >> 1 is equivalent to n // 2.

  Source Code

import sys

def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()

    m = n >> 1
    total = sum(a)

    low = 0
    for i in range(m):
        low += a[i]

    if n & 1:
        high = total - low - a[m]
        ans = 2 * (high - low) - min(a[m] - a[m - 1], a[m + 1] - a[m])
    else:
        ans = 2 * (total - 2 * low) - (a[m] - a[m - 1])

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.