Stick Lengths

Stick Lengths
CSES medium

You are given \(n\) sticks with lengths \(p_1, p_2, \dots, p_n\). You want to make all sticks the same length.

You may either lengthen or shorten each stick. Changing the length of a stick from \(a\) to \(b\) costs \(|a-b|\).

Task: Find the minimum total cost to make all sticks have the same length.

Constraints:

  • \(1 \le n \le 2 \cdot 10^5\)
  • \(1 \le p_i \le 10^9\)

Input:

  • First line: integer \(n\) — number of sticks.
  • Second line: \(n\) integers \(p_1, p_2, \dots, p_n\) — the stick lengths.

Output:

  • One integer — the minimum possible total cost.

Example:

Input:

5
2 3 1 5 2

Output:

5