Overview

When rearranging the thicknesses of books, the value that minimizes the sum of absolute differences between adjacent thicknesses is actually \(M - m\) (maximum value − minimum value).

Analysis

At first glance, this appears to be a problem of finding the “optimal arrangement,” so one might consider brute force (\(N!\) permutations) or DP approaches that handle permutations. However, since \(N \le 2\times 10^5\), these approaches are far too slow.

The key observations are the following two points.

1. The lower bound for any arrangement is \(M-m\)

Let the minimum thickness be \(m=\min(V)\) and the maximum thickness be \(M=\max(V)\).
No matter what permutation is used, \(m\) and \(M\) must appear somewhere in the arrangement.

Consider the interval from the position of \(m\) to the position of \(M\) in the arrangement. The sum of adjacent differences in this interval satisfies

\[ |a_{k+1}-a_k| + |a_{k+2}-a_{k+1}| + \cdots + |a_\ell-a_{\ell-1}| \ge |a_\ell-a_k| \]

(by the triangle inequality for absolute values), which gives

\[ \ge |M-m| = M-m \]

Since the total sum is at least as large as the sum over this interval, the answer is always at least \(M-m\) for any arrangement.

2. Sorting in ascending (or descending) order achieves exactly \(M-m\)

If we sort the thicknesses in ascending order as \(b_1 \le b_2 \le \cdots \le b_N\), then

\[ \sum_{i=1}^{N-1} |b_{i+1}-b_i| = \sum_{i=1}^{N-1} (b_{i+1}-b_i) = b_N - b_1 = M - m \]

Therefore, the lower bound \(M-m\) is achievable, and the minimum value is confirmed to be \(M-m\).

Concrete Example

For \(V=[3,10,6]\), we have \(m=3, M=10\), so the answer is \(7\).
Indeed, with the ascending order \([3,6,10]\), we get \(|6-3|+|10-6|=3+4=7\), achieving this value.

Algorithm

1. Find the minimum value \(m\) and maximum value \(M\) from the array \(V\)
2. Output \(M-m\)
   (When \(N=1\), \(M=m\) so the result is \(0\))

Complexity

• Time complexity: \(O(N)\) (just a single scan to find the minimum and maximum)
• Space complexity: \(O(1)\) (almost nothing needed beyond the input array)

Implementation Notes

• Sorting itself is unnecessary; all we need is \(\min\) and \(\max\).

• Note that when \(N=1\), the difference is \(0\) (though \(\max-\min\) naturally gives \(0\) in this case as well).

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    v = data[1:1+n]
    print(max(v) - min(v) if n >= 1 else 0)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.