파일 업로드

친구 모으기

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

도시에서 수민의 NN명의 친구들은 항상 다양한 장소로 떠돌아다닙니다! 그는 친구들을 모두 한 장소에서 만나게 하고 싶은데 여러분의 도움이 필요합니다.

도시의 주요 거리는 길고 좁습니다. 우리는 그것을 숫자선으로 생각해볼 수 있으며, 친구는 어떤 정수 위치에나 있을 수 있습니다. NN명의 친구들은 현재 다른 정수 위치에 위치해 있으며, 수민은 그들이 연속적인 위치에 있도록 움직이기를 원합니다 (예: 위치 3, 4, 5, 6, 7, 그리고 8).

불행히도 친구들은 게으르며, 수민은 그들의 주의를 끌어 움직이게 하는데 어려움을 겪습니다. 그는 어느 시점에서든지 친구를 움직일 수 있지만, 그 친구가 "끝점"일 때 (즉, 모든 친구들 중에서 최소 위치 또는 최대 위치일 때)만 가능합니다. 그가 친구를 움직일 때, 그는 그 친구가 더 이상 "끝점"이 아닌 새로운 위치로 아무렇게나 빈 정수 위치로 그 친구를 움직일 수 있도록 지시할 수 있습니다. 시간이 지나면서, 이런 유형의 움직임은 친구들이 점점 더 가까워지도록 만듭니다.

친구들이 NN개의 연속된 위치에 모이기 전에 최소 움직임 수와 최대 움직임 수를 결정해 주시기 바랍니다.

💻 입력

입력의 첫 줄에는 NN (3N1053 \leq N \leq 10^5)이 포함됩니다. 다음 NN 줄 각각에는 단일 친구의 정수 위치가 포함되며, 범위는 11091 \ldots 10^9입니다.

🖨️ 출력

출력의 첫 줄은 수민이 친구들을 함께 모으기 위해 움직여야 하는 최소 움직임 수를 포함해야 합니다. 

출력의 두 번째 줄에는 친구들이 함께 모이기 전에 그가 생각할 수 있는 최대 움직임 수를 포함해야 합니다.


💻 예제 입력 1
3
7
4
9
🖨️ 예제 출력 1
1
2

💡 힌트

최소 움직임 수는 1입니다. 

만약 수민이 4 위치에 있는 친구를 8 위치로 움직이면, 친구들은 연속적인 위치 7, 8, 9에 있게 됩니다. 

최대 움직임 수는 2입니다. 

예를 들어, 9 위치에 있는 친구가 6 위치로 이동할 수 있고, 그리고 나서 7 위치에 있는 친구가 5 위치로 이동할 수 있습니다.


출처: USACO 2019 February Contest, Silver Problem 1. Sleepy Cow Herding