Overview

This problem asks to maximize the sum of absolute differences between adjacent values when \(N\) values \(A_i\) are rearranged in any order.

The maximum is achieved by sorting the values and alternately placing elements from the group of small values and the group of large values.

Analysis

First, the indices of the artworks themselves have no significance; only the tone values \(A_i\) matter.
Therefore, we sort the values in ascending order and work from there.

Let \(A\) denote the sorted array.

The difference between two adjacent values \(|x-y|\) equals the larger value minus the smaller value.
In other words, each value becomes either “added” or “subtracted” depending on its neighbor.

The key observations are:

• Large values should be “added” as many times as possible
• Small values should be “subtracted” as many times as possible
• Each element appears in adjacent differences at most 2 times if it is in the interior of the sequence, or 1 time if it is at an endpoint

Therefore, to maximize the sum, we should alternate small and large values as much as possible.

For example, placing two small values or two large values next to each other does not produce a large difference.
On the other hand, placing a small value next to a large value creates a large difference.

Naively trying all permutations gives \(N!\) possibilities, which is far too slow for \(N \leq 10^6\).
Instead, we use the properties of the sorted values to directly compute the maximum with a formula.

---

When \(N\) is even

Let \(N = 2m\).

Split the sorted array into the first \(m\) elements and the last \(m\) elements.

• Small side: \(A_0, A_1, \ldots, A_{m-1}\)
• Large side: \(A_m, A_{m+1}, \ldots, A_{2m-1}\)

When alternating between the small side and the large side, most elements appear in the differences 2 times each.

Ideally,

• All elements on the large side are added \(2\) times
• All elements on the small side are subtracted \(2\) times

giving:

\(2 \times (\text{sum of large side} - \text{sum of small side})\)

However, the elements at both endpoints of the sequence are used only 1 time.
When the count is even, the endpoints have one element from the small side and one from the large side.

To minimize the loss, we should place the values closest to the boundary at the endpoints:

• The maximum of the small side: \(A_{m-1}\)
• The minimum of the large side: \(A_m\)

Thus the maximum value is:

\(2 \times (\text{sum of large side} - \text{sum of small side}) - (A_m - A_{m-1})\)

In code, this is computed as:

\(2 \times (\text{high} - \text{low}) + A_{m-1} - A_m\)

---

When \(N\) is odd

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

Split the sorted array as follows:

• Small side: \(A_0, A_1, \ldots, A_{m-1}\)
• Center: \(A_m\)
• Large side: \(A_{m+1}, A_{m+2}, \ldots, A_{2m}\)

We consider two cases: placing the center value \(A_m\) into the small side or into the large side.

---

Case 1: Center is placed into the small side

The small side has \(m+1\) elements and the large side has \(m\) elements.

In this case, alternating places the small side at both endpoints.
Since elements at the endpoints are subtracted only 1 time, it is beneficial to place the largest possible values at the endpoints.

The two largest values in the small side are:

• \(A_{m-1}\)
• \(A_m\)

The value in this case is:

\(2 \times (\text{high} - \text{low}) + A_{m-1} - A_m\)

---

Case 2: Center is placed into the large side

The small side has \(m\) elements and the large side has \(m+1\) elements.

In this case, alternating places the large side at both endpoints.
Since elements at the endpoints are added only 1 time, it is best to place the smallest possible values at the endpoints to minimize loss.

The two smallest values in the large side are:

• \(A_m\)
• \(A_{m+1}\)

The value in this case is:

\(2 \times (\text{high} - \text{low}) + A_m - A_{m+1}\)

Therefore, when \(N\) is odd, we take the larger of these two cases as the answer.

Algorithm

1. Sort array \(A\) in ascending order
2. If \(N = 1\), there are no adjacent elements, so the answer is \(0\)
3. Let \(m = \lfloor N/2 \rfloor\)
4. Compute the sum of the small side low
5. If \(N\) is even:
   • Compute the sum of the large side high
   • The answer is
     \(2 \times (\text{high} - \text{low}) + A_{m-1} - A_m\)
6. If \(N\) is odd:
   • Compute the sum of the large side high excluding the center \(A_m\)
   • Compare the following two cases:
     • Center placed into the small side: \(A_{m-1} - A_m\)
     • Center placed into the large side: \(A_m - A_{m+1}\)
   • The answer is
     \(2 \times (\text{high} - \text{low}) + \max(A_{m-1} - A_m,\ A_m - A_{m+1})\)

Complexity

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

Sorting is the most expensive operation.
Computing the sums takes \(O(N)\).

Implementation Notes

• When \(N = 1\), the answer is \(0\), so handle this case first.

• The answer can be approximately \(10^{15}\) at most, so long long is required in C++ and similar languages.

• In Python, integers have arbitrary precision, so no special handling is needed.

• In the code, << 1 means “multiply by 2”. For example, x << 1 is the same as 2 * x.

  Source Code

import sys

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

    if N == 1:
        print(0)
        return

    m = N >> 1
    total = sum(A)
    low = sum(A[:m])

    if N & 1:
        high = total - low - A[m]
        add1 = A[m - 1] - A[m]
        add2 = A[m] - A[m + 1]
        ans = ((high - low) << 1) + (add1 if add1 > add2 else add2)
    else:
        high = total - low
        ans = ((high - low) << 1) + A[m - 1] - A[m]

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.