Overview

The total time spent inspecting all shelves is constant, regardless of the inspection order.
Therefore, we only need to minimize the “travel time”.

Analysis

The inspection time \(T_i\) for each shelf \(i\) is added exactly once, regardless of the inspection order.

Therefore, the total inspection time

\(T_1 + T_2 + \cdots + T_N\)

is fixed.

Thus, we can rephrase this problem as follows:

Find the minimum travel distance required to start from shelf \(S\) and visit all shelves from shelf \(1\) to shelf \(N\).

Since the shelves are arranged in a straight line, to inspect all shelves, we must visit both the leftmost shelf \(1\) and the rightmost shelf \(N\).

There are two main ways to start from shelf \(S\) and visit both ends:

1. Go to shelf \(1\) first, then go to shelf \(N\).
   The travel distance is
   \((S - 1) + (N - 1)\)

2. Go to shelf \(N\) first, then go to shelf \(1\).
   The travel distance is
   \((N - S) + (N - 1)\)

In both cases, we must travel the distance of \(N - 1\) between shelf \(1\) and shelf \(N\).
Additionally, we need the distance to reach one of the ends first.

Therefore, the minimum travel distance is

\((N - 1) + \min(S - 1, N - S)\)

For example, consider the case where \(N = 7, S = 3\).

• Going to the left end first:
  Shelf \(3 \to 1 \to 7\)
  The travel distance is \(2 + 6 = 8\).

• Going to the right end first:
  Shelf \(3 \to 7 \to 1\)
  The travel distance is \(4 + 6 = 10\).

Thus, the minimum travel distance is \(8\).

Since the travel time between adjacent shelves is \(D\) minutes, the travel time is

\(\left((N - 1) + \min(S - 1, N - S)\right) \times D\)

A naive brute-force search over all inspection orders would require checking all permutations, resulting in \(O(N!)\) time complexity, which is far too slow for \(N \leq 10^6\).
However, because the inspection time is fixed regardless of the order, and we only need to consider visiting the endpoints \(1\) and \(N\) for travel, we can calculate the answer using a simple formula.

Algorithm

1. Find the total inspection time. $\( \text{total} = \sum_{i=1}^{N} T_i \)$

2. Find the minimum travel distance. $\( \text{move\_steps} = (N - 1) + \min(S - 1, N - S) \)$

3. Find the travel time. $\( \text{move\_time} = \text{move\_steps} \times D \)$

4. The answer is the sum of the total inspection time and the total travel time. $\( \text{answer} = \text{total} + \text{move\_time} \)$

Complexity

• Time Complexity: \(O(N)\)
• Space Complexity: \(O(N)\)

Implementation Notes

Since \(N\) can be as large as \(10^6\), the input should be read quickly (for example, using sys.stdin.buffer.read() in Python).

Also, the answer can be very large.

• The total inspection time can be up to \(10^6 \times 10^9 = 10^{15}\).
• The travel time can also be up to approximately \(10^6 \times 10^9 = 10^{15}\).

Python’s integer type handles arbitrarily large integers automatically, but in other languages, you must use a 64-bit integer type (such as long long in C++).

Source Code

import sys

data = list(map(int, sys.stdin.buffer.read().split()))
N, D, S = data[0], data[1], data[2]
total_inspection = sum(data[3:])

move_steps = (N - 1) + min(S - 1, N - S)
ans = total_inspection + move_steps * D

print(ans)

---

This editorial was generated by gpt-5.5-high.