Overview

Arrange \(N\) values in any order, select exactly \(K\) edges from adjacent positions, and find the maximum sum of absolute differences.

The key insight is that instead of directly considering the actual arrangement, we think about “how many times each value appears with a plus or minus sign in the total sum.”

Analysis

First, let the elevations sorted in ascending order be

\[ B_1 \leq B_2 \leq \cdots \leq B_N \]

When we select one suspension bridge with elevations \(x \leq y\) at its endpoints, the added value is

\[ y - x \]

This can be thought of as assigning coefficients:

• \(+1\) to the larger value
• \(-1\) to the smaller value

For example, if a bridge connects \(3\) and \(10\), the contribution is

\[ 10 - 3 \]

so \(10\) gets \(+1\) and \(3\) gets \(-1\).

---

Looking only at the \(K\) selected suspension bridges, since they are a subset of adjacent edges on a line, each vertex has degree at most \(2\).

Therefore, the coefficient assigned to each value is one of the following:

\[ -2, -1, 0, 1, 2 \]

Also, since each bridge produces exactly one \(+1\) and one \(-1\),

• The sum of positive coefficients is \(K\)
• The sum of negative coefficients is \(-K\)

Furthermore, the selected edges form a collection of paths. A path with one or more edges always has exactly 2 endpoints, and endpoints have degree \(1\).

Since vertices with degree \(1\) have coefficient \(+1\) or \(-1\), at least 2 odd coefficients are required.

---

To maximize the sum:

• Assign large positive coefficients to large values
• Assign large negative coefficients to small values

In other words, we want to assign as many:

• \(-2\) to small values
• \(+2\) to large values

as possible.

However, \(+1\) and \(-1\) coefficients are also needed to create endpoints.

---

Case when \(K\) is odd

Let \(K = 2m - 1\).

To make the sum of positive coefficients equal to \(K\), the optimal choice is:

• \(m-1\) coefficients of \(+2\)
• \(1\) coefficient of \(+1\)

Similarly for negative coefficients:

• \(m-1\) coefficients of \(-2\)
• \(1\) coefficient of \(-1\)

Therefore, assign:

• \(-2\) to the smallest \(m-1\) values
• \(-1\) to the next one, \(B_m\)
• \(+2\) to the largest \(m-1\) values
• \(+1\) to the next one, \(B_{N-m+1}\)

The answer is

\[ 2 \left( \sum_{i=N-m+2}^{N} B_i - \sum_{i=1}^{m-1} B_i \right) + B_{N-m+1} - B_m \]

---

Case when \(K\) is even

Let \(K = 2m\).

A naive approach would be to assign:

• \(-2\) to the smallest \(m\) values
• \(+2\) to the largest \(m\) values

However, this makes all coefficients even, and no path endpoints exist.

Therefore, we need to create coefficients of \(+1\) or \(-1\) somewhere.

Since \(K\) is even, both the number of \(+1\) coefficients and the number of \(-1\) coefficients must be even.

The optimal candidates are the following two options:

---

Candidate 1: Create endpoints on the lower side

• \(+2\) to the largest \(m\) values
• \(-2\) to the smallest \(m-1\) values
• \(-1\) to \(B_m, B_{m+1}\)

The value in this case is

\[ S_1 = 2 \sum_{i=N-m+1}^{N} B_i - 2 \sum_{i=1}^{m-1} B_i - B_m - B_{m+1} \]

---

Candidate 2: Create endpoints on the upper side

• \(-2\) to the smallest \(m\) values
• \(+2\) to the largest \(m-1\) values
• \(+1\) to \(B_{N-m}, B_{N-m+1}\)

The value in this case is

\[ S_2 = 2 \sum_{i=N-m+2}^{N} B_i + B_{N-m} + B_{N-m+1} - 2 \sum_{i=1}^{m} B_i \]

Therefore, the answer is

\[ \max(S_1, S_2) \]

---

These coefficient assignments can actually be achieved by alternating low and high values.

For example, when creating endpoints on the lower side, arrange as:

\[ \text{low} - \text{high} - \text{low} - \text{high} - \cdots - \text{low} \]

This way, internal high values get \(+2\), internal low values get \(-2\), and the two endpoint low values get \(-1\).

Algorithm

1. Sort array \(A\) in ascending order to get \(B\).
2. Split into cases based on the parity of \(K\).
3. If \(K\) is odd, compute the answer using the formula for the odd case.
4. If \(K\) is even, compute \(S_1, S_2\) and take the larger one as the answer.

In the code, 0-indexed arrays are used, so for example \(B_m\) corresponds to A[m-1].

Complexity

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

Sorting is the most expensive operation.

Implementation Notes

Since \(N\) can be as large as \(10^6\), input must be read efficiently.

Also, the answer can be as large as \(10^9 \times 10^6 = 10^{15}\), so in C++ and similar languages, the long long type is required. In Python, integers have arbitrary precision, so no special handling is needed.

Source Code

import sys

def main():
    data = sys.stdin.buffer.read()
    L = len(data)
    i = 0

    while i < L and data[i] <= 32:
        i += 1
    N = 0
    while i < L and data[i] > 32:
        N = N * 10 + data[i] - 48
        i += 1

    while i < L and data[i] <= 32:
        i += 1
    K = 0
    while i < L and data[i] > 32:
        K = K * 10 + data[i] - 48
        i += 1

    A = [0] * N
    for j in range(N):
        while i < L and data[i] <= 32:
            i += 1
        x = 0
        while i < L and data[i] > 32:
            x = x * 10 + data[i] - 48
            i += 1
        A[j] = x

    del data

    A.sort()

    if K & 1:
        m = (K + 1) >> 1
        t = m - 1
        low = sum(A[:t])
        high = sum(A[N - t:]) if t else 0
        ans = (high - low) * 2 + A[N - m] - A[m - 1]
    else:
        m = K >> 1
        t = m - 1
        low = sum(A[:t])
        high = sum(A[N - t:]) if t else 0

        bottom_m = low + A[m - 1]
        top_m = high + A[N - m]

        ans1 = top_m * 2 - low * 2 - A[m - 1] - A[m]
        ans2 = high * 2 + A[N - m - 1] + A[N - m] - bottom_m * 2
        ans = ans1 if ans1 > ans2 else ans2

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.