Overview

When the tempo values are sorted in ascending order, only the boundaries where the difference between adjacent values exceeds \(D\) will inevitably cause discomfort.
The answer is the sum of the differences between adjacent values that are greater than \(D\) after sorting.

Analysis

Let the tempo values sorted in ascending order be:

\[ X_1 \leq X_2 \leq \cdots \leq X_N \]

Let us focus on the difference between adjacent values, \(X_{i+1} - X_i\).

When the difference is \(D\) or less

\[ X_{i+1} - X_i \leq D \]

If this holds, playing \(X_{i+1}\) immediately after \(X_i\) results in a discomfort score of \(0\) because \(X_{i+1}\) is similar to the preceding song.

In other words, as long as we play the songs in ascending order, no discomfort occurs in parts where the difference is \(D\) or less.

When the difference is greater than \(D\)

On the other hand, if

\[ X_{i+1} - X_i > D \]

then any song with a tempo of \(X_i\) or less and any song with a tempo of \(X_{i+1}\) or more are not similar to each other.

To cross this boundary and play all songs on both sides, we must at some point play a song for which “no similar song has been played in the past.”

At that moment, a discomfort score of at least this difference:

\[ X_{i+1} - X_i \]

will be incurred.

Playing in ascending order is optimal

Indeed, if we play the songs in ascending order:

• The discomfort score is \(0\) in parts where the difference is \(D\) or less.
• The discomfort score is exactly the difference itself in parts where the difference is greater than \(D\).

Therefore, the answer is the sum of the “adjacent differences greater than \(D\)” when sorted in ascending order.

For example, if

\[ A = [1, 3, 4, 10, 12], \quad D = 2 \]

then the adjacent differences after sorting are

\[ 2, 1, 6, 2 \]

Among these, only \(6\) is greater than \(D = 2\), so the answer is \(6\).

In fact, if we play them in the order of

\[ 1 \to 3 \to 4 \to 10 \to 12 \]

discomfort only occurs when transitioning from \(4\) to \(10\).

Naively trying all possible playing orders would take \(N!\) operations, which is impossible for \(N \leq 10^6\).
Also, checking all past songs for each song would take \(O(N^2)\) time, which is too slow.

However, it is sufficient to simply sort the values and check the adjacent differences.

Algorithm

1. Sort the array \(A\) in ascending order.
2. Iterate through the differences between adjacent elements.
3. If a difference is greater than \(D\), add that difference to the answer.
4. Output the final answer.

In other words, the answer is:

\[ \sum_{i=1}^{N-1} \begin{cases} A_{i+1} - A_i & \text{if } A_{i+1} - A_i > D \\ 0 & \text{otherwise} \end{cases} \]

Note that \(A\) here represents the sorted array.

Complexity

• Time Complexity: \(O(N \log N)\)
  • \(O(N \log N)\) for sorting
  • \(O(N)\) for the subsequent scan
• Space Complexity: \(O(N)\)
  • To store the array \(A\)

Implementation Points

Since \(N\) can be as large as \(10^6\), fast I/O is necessary.

In Python, using sys.stdin.buffer.read() is fast.

Also, the answer can potentially be very large. Since Python’s int has arbitrary precision, you do not need to worry about overflow. If you are implementing in languages like C++, you must use a 64-bit integer type such as long long.

Source Code

import sys

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

    ans = 0
    prev = A[0]
    for x in A:
        diff = x - prev
        if diff > D:
            ans += diff
        prev = x

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.5-high.