Problem B
Excursion
Languages
en
sv
No IOI is complete without at least one excursion. This year, all contestants will go to Cal Orck’o, an archaeological site with dinosaur footprints outside Sucre. The organizers have arranged two infinitely large buses to transport all participants to the site.
There are $N$ participants going on the excursion. The $i$th participant is ready to go at time $t_i$. If a bus departs at time $T$, then all participants satisfying $t_i \leq T$ can board the bus. The waiting time of participant $i$ is then $T-t_i$.
Your task is to compute the smallest possible total waiting time $v_1+v_2+\dots +v_N$ if the two buses’ departure times are chosen optimally. Every participant must travel with one of the buses, and each of the buses can only depart once.
Input
The first line contains one integer $N$ ($2 \leq N \leq 3 \cdot 10^5$), the number of participants.
The following $N$ lines contain one integer $t_i$ ($1 \leq t_i \leq 10^9$) each, the times when the participants are ready to go.
Output
Print one integer, the smallest possible total waiting time $v_1+v_2+\dots +v_N$.
Scoring
Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.
|
Group |
Points |
Constraints |
|
$1$ |
$17$ |
$N \leq 100$, $t_i \leq 300$ |
|
$2$ |
$26$ |
$N \leq 1000$ |
|
$3$ |
$25$ |
$t_i = i$ for every $i = 1,2,\dots , N$ |
|
$4$ |
$32$ |
No additional constraints. |
Explanation of Sample 1
In the first sample, it is optimal to let the three first participants go with a bus that departs at $T = 4$, and the three last go with the other bus that departs at $T = 11$.
| Sample Input 1 | Sample Output 1 |
|---|---|
6 2 4 1 10 8 11 |
9 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 1 2025 |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
20 1 50000001 100000001 150000001 200000001 250000001 300000001 350000001 400000001 450000001 500000001 550000001 600000001 650000001 700000001 750000001 800000001 850000001 900000001 950000001 |
4500000000 |
