그저 긴 목걸이들 timer 2초 memory 512MB

Just Odd Inventions 회사를 알고 계십니까? 이 회사의 업무는 "단지 이상한 발명 (just oddinventions)"을하는 것입니다. 여기서는 약어 JOI 사라고 부른다.

JOI 사는 신상품 "긴 넥타이"를 개발했다. 넥타이는 N + 1 종류가 있으며 각 종류에는 1에서 N + 1까지의 번호가 붙어 있습니다. i 번째 (1≤i≤N + 1) 유형의 넥타이 길이는 Ai입니다.

JOI 사는 직원을 모아 넥타이의 시착회를 실시하기로 했다. 시착회에는 N명의 직원이 참가하고, j번째(1≤j≤N)의 직원이 처음 붙이고 있는 넥타이의 길이는 Bj이다.

시착회는 이하의 순서로 행해질 예정이다.

1. 우선, 시착회에서 사용하지 않는 넥타이를 1 종류 선택한다.

2. 다음으로 각 직원은 다른 넥타이에서 착용 할 넥타이 중 하나를 선택합니다. 그러나 두 사람 모두 같은 종류의 넥타이를 선택하지 않습니다.

3. 마지막으로, 각 직원은 지금 붙이고있는 넥타이를 제거하고 방금 선택한 넥타이를 시도합니다.

길이 b의 넥타이를 붙인 직원이 길이 a의 넥타이를 시도하면 크기 max {a - b, 0}의 이상함을 느낀다. (여기서, max {a - b, 0}은 a - b와 0 중 작지 않은 쪽을 나타낸다.) 시착회에서 각 직원이 느끼는 기묘함의 최대치를 그 시착회의 기묘함으로 한다.

시착회에서 사용하지 않는 넥타이가 k 번째의 종류의 넥타이일 때, 시착회의 기묘함으로 생각되는 최소값을 Ck로 한다.

각 종류의 넥타이의 길이, 각 직원이 처음에 붙이고 있는 넥타이의 길이가 주어졌을 때, C1, C2, .., CN+1의 값을 구하는 프로그램을 작성하라.