Overview

This is a problem where you freely rearrange \(N\) books and minimize the sum of absolute differences in thickness between adjacent books.

Analysis

The key point of this problem is to determine “in what order should the books be arranged to minimize the total difference.”

Intuitive Observation

For example, consider 3 books with thicknesses \(10, 30, 20\). - Arranged as \([10, 30, 20]\): \(|30 - 10| + |20 - 30| = 20 + 10 = 30\) - Arranged as \([10, 20, 30]\): \(|20 - 10| + |30 - 20| = 10 + 10 = 20\)

As we can see, arranging the values in ascending (or descending) order seems to result in a smaller total difference.

Mathematical Justification

Let the books sorted in ascending order of thickness be \(A_1, A_2, \dots, A_N\) (\(A_1 \leq A_2 \leq \dots \leq A_N\)). The sum of absolute differences between adjacent elements is: \(|A_2 - A_1| + |A_3 - A_2| + \dots + |A_N - A_{N-1}|\)

Since all terms are positive (or \(0\)), we can remove the absolute value signs directly: \((A_2 - A_1) + (A_3 - A_2) + \dots + (A_N - A_{N-1})\)

Computing this, all intermediate terms cancel out, and what ultimately remains is just \(A_N - A_1\), that is, (maximum value) - (minimum value).

No matter how the books are arranged, you need to “traverse” from the minimum value to the maximum value, so the total sum cannot be less than \(A_N - A_1\). Therefore, the minimum is achieved when arranged in ascending (or descending) order.

Algorithm

1. Find the maximum value \(V_{max}\) and minimum value \(V_{min}\) among the \(N\) given thicknesses \(V_i\).
2. Compute and output \(V_{max} - V_{min}\).
3. However, when \(N=1\), there are no adjacent books, so the answer is \(0\).

Complexity

• Time complexity: \(O(N)\)
  • Since we scan the \(N\) elements once to find the maximum and minimum values, the processing time is proportional to the number of elements.
• Space complexity: \(O(N)\)
  • This is the memory required to store the \(N\) input values in a list.

Implementation Notes

• Since \(N\) can be as large as \(2 \times 10^5\), in Python it is safer to use fast I/O methods such as sys.stdin.read().split().

• The answer can potentially be very large (up to around \(10^9\)), but since Python’s integer type automatically handles arbitrary-precision integers, there is no concern about overflow.

  Source Code

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白で分割してリストにします。
    # これにより、大量の入力データ（N=2*10^5）を高速に処理できます。
    input_data = sys.stdin.read().split()
    
    # 入力が空の場合は何もせず終了します。
    if not input_data:
        return
    
    # 最初の要素は本の冊数 N です。
    n = int(input_data[0])
    
    # 本が1冊以下の場合は、隣り合う本が存在しないため、差の総和は 0 になります。
    if n < 2:
        print(0)
        return
    
    # 2番目以降の要素は各本の厚さ V_i です。
    # これらを整数のリストに変換します。
    v_values = list(map(int, input_data[1:]))
    
    # 隣り合う要素の差の絶対値の総和を最小にするには、
    # 本を厚さの昇順（または降順）に並べるのが最適です。
    # その場合、総和は (最大値 - 最小値) となります。
    # どのような並べ方でも、最小値から最大値までの移動は必ず含まれるため、
    # 総和が (最大値 - 最小値) を下回ることはありません。
    
    result = max(v_values) - min(v_values)
    
    # 結果を出力します。
    print(result)

if __name__ == "__main__":
    main()

This editorial was generated by gemini-3-flash-preview.