Overview

This is a problem where you need to find the minimum number of cuts required to make all sticks the same positive length without stretching any of them.

Analysis

• Since the only operation available is “shorten a chosen stick by \(1\) cm,” if we let the final common length be \(L\), then \(L \le A_i\) (for all sticks) must hold.
  In other words, \(L\) must satisfy \(L \le \min(A)\).
• Also, a length of \(0\) is not allowed, so \(L > 0\) is required. However, since \(A_i \ge 1\) by the constraints, we have \(\min(A) \ge 1\), so \(L = \min(A)\) always satisfies this condition.

So, which \(L\) minimizes the total number of cuts?

• To reduce stick \(i\) from \(A_i\) to \(L\), we need \(A_i - L\) cuts.
• The total number of cuts is
  $\( \sum_{i=1}^{N} (A_i - L) = \left(\sum_{i=1}^{N} A_i\right) - N L \)$
• Looking at the right-hand side, the larger \(L\) is (within the valid range), the smaller the total number of cuts becomes.
  However, since \(L\) can be at most \(\min(A)\), the optimal choice is \(L = \min(A)\).

If you naively simulate something like “always cut the longest stick,” the number of cuts can be on the order of \(\sum A_i\) (which is infeasible since \(A_i\) can be up to \(10^9\)), resulting in TLE.
This problem can be solved with a single calculation based on the observation that “the final length is determined to be the minimum value.”

Example: \(A=[5,3,7]\)
The best strategy is to make all sticks length \(\min(A)=3\). The required number of cuts is \((5-3)+(3-3)+(7-3)=2+0+4=6\).
Using the formula: \(\sum A - N\min(A)=15-3\cdot 3=6\).

Algorithm

1. Find the minimum value of array \(A\): \(mn = \min(A)\)
2. Find the total sum of the array: \(total = \sum A_i\)
3. Output the answer:
   $\( total - mn \times N \)$

Complexity

• Time complexity: \(O(N)\) (computing the minimum and the sum each in one pass)
• Space complexity: \(O(1)\) (constant space excluding the input array)

Implementation Notes

• Since \(N \le 2\times 10^5\), using sys.stdin.buffer.read() for fast input is recommended in Python.

• The answer can be as large as approximately \(N \times 10^9\), but Python’s integers do not overflow.

  Source Code

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    a = data[1:]
    mn = min(a)
    total = sum(a)
    print(total - mn * n)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.