Problem Description

There are $N$ stores on a number line, with coordinates $A_1 \sim A_N$.

Now you need to build a warehouse on the number line. Every morning, one truck of goods must be delivered from the warehouse to each store.

To improve efficiency, find where to build the warehouse so that the sum of distances from the warehouse to all stores is minimized.

Input Format

The first line contains an integer $N$.

The second line contains $N$ integers $A_1 \sim A_N$.

Output Format

Output one integer, representing the minimum possible sum of distances.

4
6 2 9 1

12

Hint

Constraints: $1 \le N \le 10^5$, $0 \le A_i \le 40000$.

Translated by ChatGPT 5