루미 알고리즘

#1608골드Excursion

PO 2025 결선코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

(그림은 원문 저장소에서 볼 수 있습니다)

Footprints at Cal Orck'o. Image (https://commons.wikimedia.org/wiki/File:Cal_Orcko_fossil_tracks_2.jpg) by John Martin Perry, CC BY-SA 4.0

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 ith participant is ready to go at time t_i. If a bus departs at time T, then all participants satisfying t_i ≤ 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+…+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 ≤ N ≤ 3 · 10^5), the number of participants.

The following N lines contain one integer t_i (1 ≤ t_i ≤ 10^9) each, the times when the participants are ready to go.

Output

Print an integer: the smallest possible total waiting time v_1+v_2+…+v_N.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
117N ≤ 100, t_i ≤ 300
226N ≤ 1000
325t_i = i for every i = 1,2,…, N
432No 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.

예제

예제 1

입력
6
2
4
1
10
8
11
출력
9

예제 2

입력
2
1
2025
출력
0

예제 3

입력
20
1
50000001
100000001
150000001
200000001
250000001
300000001
350000001
400000001
450000001
500000001
550000001
600000001
650000001
700000001
750000001
800000001
850000001
900000001
950000001
출력
4500000000

출처 표기

출처: Programmeringsolympiaden 2025년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.