Overview

This problem asks us to find the maximum possible sum of absolute differences between adjacent elements after rearranging \(N\) values \(C_i\) in any order.

The key is to sort the values in ascending order and consider an arrangement where “small values” and “large values” alternate as much as possible.

Analysis

First, let us sort the values in ascending order and denote them as:

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

A naive approach that tries all permutations would take \(N!\) time, which is far too slow since \(N \leq 10^6\).

For two adjacent values \(x\) and \(y\), if \(x < y\), their absolute difference is:

\( y - x \)

Thus, the total contrast can be thought of as the difference between:

• The sum of values that are added (as the larger of the two adjacent elements)
• The sum of values that are subtracted (as the smaller of the two adjacent elements)

Since each element interacts with at most two adjacent elements (left and right), the number of times any element is added or subtracted is at most 2.

Therefore, to maximize the sum, we intuitively want to:

• Use the larger values as \(+2\) times as much as possible
• Use the smaller values as \(-2\) times as much as possible
• Since the elements placed at the ends are only used once, we want to place the values near the middle at the ends to minimize the loss.

---

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} \)

Ideally, we want to use the larger values \(+2\) times and the smaller values \(-2\) times.

However, the elements at both ends only have one neighbor.

When \(N\) is even, if we alternate between the smaller and larger halves, the two ends will consist of one element from the smaller half and one from the larger half.

To minimize the loss, it is optimal to place the following elements at the ends:

• The maximum value of the smaller half, \(a_{m-1}\)
• The minimum value of the larger half, \(a_m\)

Thus, the maximum value is:

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

For example, in the case of \([1,2,3,4,5,6]\):

\( 2 \times ((4+5+6) - (1+2+3)) - (4-3) = 17 \)

Indeed, if we arrange them as:

\( 3, 6, 1, 5, 2, 4 \)

the sum is:

\( 3 + 5 + 4 + 3 + 2 = 17 \)

---

When \(N\) is odd

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

The median is \(a_m\).

We define the smaller half as:

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

and the larger half as:

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

Excluding the median \(a_m\), both the smaller and larger halves have \(m\) elements.

The ideal value is:

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

but the median \(a_m\) must also be placed somewhere.

Using the median will cause one of the following losses:

• If we treat the median as part of the smaller side, we suffer a loss of \(a_m - a_{m-1}\)
• If we treat the median as part of the larger side, we suffer a loss of \(a_{m+1} - a_m\)

Since we should choose the option that minimizes the loss, the maximum value 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, in the case of \([1,2,3,4,5]\):

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

Indeed, if we arrange them as:

\( 2, 4, 1, 5, 3 \)

we get:

\( 2 + 3 + 4 + 2 = 11 \)

Algorithm

1. Sort the array \(C\) in ascending order.
2. Branch based on whether \(N\) is even or odd.
3. If \(N\) is even:
   • \(m = N/2\)
   • Let the sum of the smaller half be \(\text{low} = \sum_{i=0}^{m-1} a_i\)
   • Let the sum of the larger half be \(\text{high} = \sum_{i=m}^{N-1} a_i\)
   • The answer is:
     \( 2(\text{high} - \text{low}) - (a_m - a_{m-1}) \)
4. If \(N\) is odd:
   • \(m = N/2\)
   • Let the sum of the smaller half be \(\text{low} = \sum_{i=0}^{m-1} a_i\)
   • Let the sum of the larger half be \(\text{high} = \sum_{i=m+1}^{N-1} a_i\)
   • The answer is:
     \( 2(\text{high} - \text{low}) - \min(a_m - a_{m-1}, a_{m+1} - a_m) \)
5. Output the answer.

Complexity

• Time Complexity: \(O(N \log N)\)
• Space Complexity: \(O(N)\)

Implementation Points

The answer can be up to approximately \((N-1) \times 10^9\), which can be around \(10^{15}\).

Therefore, you need to use long long instead of int.

Also, since \(N\) can be as large as \(10^6\), it is safe to include the following for fast I/O in C++:

ios::sync_with_stdio(false);
cin.tie(nullptr);

Source Code

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;

    vector<long long> C(N);
    for (int i = 0; i < N; i++) cin >> C[i];

    sort(C.begin(), C.end());

    long long ans = 0;

    if (N % 2 == 0) {
        int m = N / 2;
        long long low = 0, high = 0;

        for (int i = 0; i < m; i++) low += C[i];
        for (int i = m; i < N; i++) high += C[i];

        ans = 2 * (high - low) - (C[m] - C[m - 1]);
    } else {
        int m = N / 2;
        long long low = 0, high = 0;

        for (int i = 0; i < m; i++) low += C[i];
        for (int i = m + 1; i < N; i++) high += C[i];

        ans = 2 * (high - low) - min(C[m] - C[m - 1], C[m + 1] - C[m]);
    }

    cout << ans << '\n';
    return 0;
}

---

This editorial was generated by gpt-5.5-high.